[알고리즘] 퀵정렬

[퀵정렬]

• 기준보다 작은 값과 큰 값을 분리한 후 다시 합친다.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
• 병합 정렬과 더불어 정렬 라이브러리의 근간이 되는 알고리즘이다.
• 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)로 설정한다.
• 이상적인 경우, 분할이 절반씩 일어난다면 전체 연산 횟수로 \( O(N*logN) \)을 기대할 수 있다.
• 평균적으로 퀵 정렬은 \( O(N*logN) \)의 시간 복잡도를 갖는다. 그러나 최악의 경우, 분할이 일어나지 않아 \( O(N^2) \)의 시간 복잡도를 가질 수 있다. ( 기본 라이브러리를 통한 정렬은 최악의 경우를 고려한 설계가 되어있기 때문에 항상 늘 \(O(N*logN)\)을 보장해니 안심하도록 하자. )
• 삽입정렬과 달리 데이터가 이미 정렬되어 있는 경우에는 매우 느리게 동작한다.

---

import random
def quick_sort(datas):
    if len(datas) < 2 :
        return datas
    mid = len(datas) // 2
    small, same, big = [],[],[]
    for i in range(len(datas)):
        if datas[i] < datas[mid]:
            small.append(datas[i])
        elif datas[i] > datas[mid]:
            big.append(datas[i])
        else :
            same.append(datas[i])
    return quick_sort(small) + same + quick_sort(big)

datas = [random.choice(range(1,101)) for _ in range(20)]
print(quick_sort(datas))

 

생각보다 코드가 꽤 간단했다.

그냥 아무 값을 기준으로, 작으면 small, 크면 big, 같으면 same 리스트에 넣어준다.

quick_sort(small) + same + quick_sort(big) 을 합쳐준다.

 

단, 주의할 점은 small이나, big에 아무 요소도 안들어가는 경우도 있기 때문에

if len(datas) < 2 라는 조건식을 넣어주었다.

 

전에 게시글 처럼 len(datas) == 1로 하자 recursive error 가 떴다.

( datas = [] 일때 무한 재귀가 돌기 때문 )

 

---

• 이코테라는 책에는 좀 다른 방식의 퀵정렬 설명이 있어 이를 토대로 다시 코드를 짜보았다.

코드 참조; 나동빈 (2020). <이것이 취업을 위한 코딩 테스트다 with 파이썬>. 서울시: 한빛미디어.

import random
def quick_sort(array,start,end):
    if start >= end :                                     # 원소가 1개일 경우 종료
        return
    pivot = start                                         # pivot은 첫번째 요소
    left = start + 1                                      # left는 pivot 다음 요소부터 시작
    right = end                                           # right 끝에서 반대방향으로 시작
    while (left <= right):                                # left와 right가 엇갈리면 종료
        while ((left <= end) and (array[left] <= array[pivot])): # pivot vlaue 보다 큰 left를 발견하기 전까지 left 증가
            left += 1
        while ((right>start) and (array[right]>= array[pivot])): # pivot value 보다 작은 right 발견하기 전까지 right 감소 
            right -= 1
        if left > right:                                          # left와 right가 엇깔리면 right 자리에 pivot을 넣는다.
            array[right],array[pivot] = array[pivot],array[right] # right과 left가 엇깔린 상태이기 때문에, right 자리에 pivot보다 작은 값이 있을거기 때문
        else :
            array[left],array[right] = array[right],array[left] # pivot 보다 작은 요소가 right에 있고, 큰 요소가 left에 있다면, 위치를 스위치 한다.
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)
mylist = [random.choice(range(1,101)) for _ in range(20) ]
quick_sort(mylist,0,len(mylist)-1)
print(mylist)

처음에 짠 코드와 달리, 리스트를 여러개 만들지 않기 때문에 낭비가 덜하다고 하다.

 

코드가 꽤 복잡해서 자주 써먹으려면 꽤 많이 코드를 연습해봐야할 것 같다.