퀵 정렬(Quick Sort) [Python / 파이썬]

1. 퀵 정렬

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 

퀵 정렬에서는 피벗(Pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식을 기준으로 퀵 정렬을 정리해 보도록 하겠다.

 

호어 분할 방식에서는 리스트의 첫 번째 데이터를 피벗으로 정한다.

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

 

자세한 과정을 아래 그림으로 살펴보자.

 

 

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

 

 

 

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

 

 

 

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

 

 

 

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

 

이런 상태에서 왼쪽 리스트와 오른쪽 리스트를 개별적으로 퀵 정렬을 수행한다.

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

 

1.1 구현 소스 코드

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))

 

---

2. 퀵 정렬의 시간 복잡도

압서 다룬 선택 정렬은 시간 복잡도가 O(N^2)이었고 삽입 정렬은 모든 원소가 정렬되어 있는 상태인 최선의 경우 O(N)

최악의 경우 O(N^2)의 시간 복잡도를 가진다. 퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다.

시간 복잡도가 O(NlogN)이 되는 이유를 간단하게 증명하자면

N = 8개의 요소가 있다고 가정해보자 이때 분할된 리스트의 요소 수는 대략 4 -> 2 -> 1으로 분할된다. 대략 3(log8) 번의 분할 과정이 필요하다. 또한 각 분할마다 모든 요소를 확인해야 하므로 총 연산 횟수는 8log8이 된다. 따라서 시간 복잡도는 N개의 요소가 있을 때 평균적으로 O(NlogN)의 시간 복잡도를 가지게 된다.

하지만 최악의 경우 퀵 정렬의 시간 복잡도는 O(N^2)이 되는데 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.  이경우 N = 8개의 요소가 있다고 가정할 때 분할된 리스트의 요소 수는 7 -> 6 -> 5 ->... -> 1이 되므로 최악의 경우 O(N^2)의 시간 복잡도를 가지게 된다.