퀵 정렬 (Quick Sort)

기준이 되는 요소(pivot)을 하나 정해서 그 요소를 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 몰아넣고 그것들을 다시 반복해서 정렬하여 합치는 알고리즘이다.(divide and conquer)

시간 복잡도

Best - O(NlogN)

Average - O(NlogN)

Worst - O(N^2)

설명

pivot을 하나 정한다. 그 후에 시작과 끝의 인덱스를 각각 left와 right로 정한다.

 

left는 pivot보다 큰 요소를 찾을 때까지 증가시킨다.

 

right는 pivot보다 작은 요소를 찾을 때까지 감소시킨다.

 

만약 left가 pivot보다 큰 요소를 찾았고 right가 pivot보다 작은 요소를 찾았다면 서로 자리를 바꿔준다.

 

그런데 만약 이 때 left와 right가 서로 교차하여 left의 값이 right보다 커져버렸다면, right와 pivot을 서로 자리를 바꿔준다.

 

그렇다면 pivot을 기준으로 두 개의 배열이 나눠지게 될 것이다. 각 배열에서 위 행위를 배열의 요소가 한 개일 때까지 똑같이 반복한다.

 

그후에 전부 합치면 정렬이 완료된다.

구현(파이썬)

일반적인 경우

def quick_sort(arr, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end and arr[left] <= arr[pivot]:
            left += 1

        while right > start and arr[right] >= arr[pivot]:
            right -= 1

        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:
            arr[left], arr[right] = arr[right], arr[left]

    quick_sort(arr, 0, right - 1)
    quick_sort(arr, right + 1, end)

arr = [6, 5, 1, 4, 7, 2, 3]
quick_sort(arr, 0, len(arr) - 1)

파이써닉한 코드

arr = [6, 5, 1, 4, 7, 2, 3]

def quick_sort(arr):

    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    tail = arr[1:]

    left_list = [x for x in tail if x <= pivot]
    right_list = [x for x in tail if x > pivot]

    return quick_sort(left_list) + [pivot] + quick_sort(right_list)

print(quick_sort(arr))