퀵 정렬

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 다음 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에서는 pivot이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 pivot이라고 표현한다. 퀵 정렬을 수행하기 전에는 pivot을 어떻게 설정할 것인지 미리 명시해야 한다.

• 리스트에서 첫 번째 데이터를 pivot으로 정한다.

이와 같이 pivot을 설정한 뒤에는 왼쪽에서부터 pivot보다 큰 데이터를 찾고, 오른쪽에서부터 pivot보다 작은 데이터를 찾는다. 그다음 큰 데이터와 작은 데이터의 위치를 서로 교환해준다. 이러한 과정을 반복하면 'pivot'에 대하여 정렬이 수행된다.

다음과 같이 초기 데이터가 구성되어 있다고 가정해보자.

Ⅰ파트

STEP 0 ) 리스트의 첫 번째 데이터를 pivot으로 설정하므로 pivot은 '5'이다. 이후에 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고, 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 두 데이터의 위치를 서로 변경한다.

STEP 1 ) 그다음 다시 pivot보다 큰 데이터와 작은 데이터를 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 '9'와 '2'가 선택되었으므로 이 두 데이터의 위치를 서로 변경한다.

STEP 2 ) 그다음 다시 pivot보다 큰 데이터와 작은 데이터를 찾는다. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우에는 '작은 데이터'와 'pivot'의 위치를 서로 변경한다. 즉, 작은 데이터인 '1'과 pivot인 '5'의 위치를 서로 변경하여 분할을 수행한다.

STEP 3) 분할 완료 이와 같이 pivot이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보면 이제 '5'의 왼쪽에 있는 데이터는 모두 '5'보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는 특징이 있다. 이렇게 pivot의 왼쪽에는 pivot보다 작은 데이터가 위치하고, pivot의 오른쪽에는 pivot보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

이러한 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 정렬 시키면 어차피 왼쪽 리스트는 어떻게 정렬되어도 모든 데이터가 '5'보다 작다. 마찬가지로 오른쪽 리스트 또한 어떻게 정렬되어도 모든 데이터가 '5'보다 크다. 따라서 왼쪽 리스트와 오른쪽 리스트에서도 각각 pivot을 설정하여 동일한 방식으로 정렬을 수행하면 전체 리스트에 대하여 모두 정렬이 이루어질 것이다.

Ⅱ파트

왼쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

Ⅲ파트

오른쪽 리스트에서는 다음 그림과 같이 정렬이 진행되며 구체적인 정렬 과정은 동일하다.

퀵 정렬의 파이썬 소스코드는 다음과 같다.

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

def quick_sort(array, start, end):
    if start >= end:
        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)

위 같이 코드를 작성하면 이러한 결과를 도출해 낼 수 있다.

퀵 정렬의 시간 복잡도

선택 정렬과 삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 삽입 정렬은 최악의 경우에도 항상 시간 복잡도는 O(N^2)을 보장한다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 앞서 말한 두 정렬 알고리즘에 비해 매우 빠른 편이다.
다만, 퀵 정렬의 시간 복잡도에 대하여 한 가지 중요하게 기억해둘 점이 있다. 바로 평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(N^2)이라는 것이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 위의 예시처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다. 삽입 정렬은 이미 데이터가 정렬되어 있는 경우에는 매우 빠르게 동작하는데 퀵 정렬은 그와 반대된다고 이해할 수 있다.