[Python][이코테] 퀵 정렬

퀵 정렬

퀵 정렬은 이름대로 굉장히 빠른 정렬을 해주는 알고리즘이다.

 

또한 굉장히 많이 쓰인다.

 

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

 

이게 퀵 정렬의 기본이다.

 

과정

1. 리스트 안에 있는 한 요소를 선택한다. 이를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈다.
3. 먼저 사용된 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 기준으로 피벗을 각자 정해 다시 정렬한다.
4. 나눠진 리스트들이 분할이 불가능할 때까지 반복한다.

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: #원소가 1개인 경우 종료
        return
    
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
            
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
            
        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
            
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)
    
quick_sort(array, 0, len(array)-1)
print(array)

코드를 보면 알겠지만 기본적으로 재귀를 활용하며

 

재귀의 종료 조건은 앞서 말한 4번 항목을 사용한다.

 

 

 

 

위의 코드를 좀 더 파이썬스럽게 꾸민다면

 

#6-4 정렬 퀵 정렬2.py
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x> pivot] # 분할된 오른쪽 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot]+quick_sort(right_side)

print(quick_sort(array))

 

좀 더 간단하게 바꿀 수 있다.

 

 

시간 복잡도

 

앞서 배운 선택 정렬과 삽입 정렬의 시간 복잡도는 $O(N^2)$이며, 최악의 경우도 $O(N^2)$을 보장한다.
하지만 퀵 정렬의 시간 복잡도는 $O(NlogN)$이다.

 

앞의 logN은 log₂N ≒ 10 정도로 계산하여 평균적인 데이터의 개수당 연산 횟수를 구하면

 

아래의 표와 같다.

 

데이터의 개수(N)	선택정렬, 삽입정렬(N²)	퀵 정렬 (Nlog₂N)
N=1000	≒ 1000000	≒10000
N=1000000	≒100000000000	≒20000000

 

N² 의 연산을 하는 선택, 삽입 정렬보다 훨씬 적은 연산 횟수로 빠른 속도를 보여주는 것을 알 수 있다.

 

다만 퀵 정렬은 '평균적인' 시간 복잡도가 O(NlogN)인 거지 최악의 경우 시간 복잡도는 O(N²)이다.

 

데이터가 무작위로 입력될 때 퀵 정렬이 매우 빠르지만

 

최악의 경우는 '이미 데이터가 정렬되어 있는 경우' 매우 느리다.

 

---

이미지 출처

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html