QuickSort (퀵 소트)

퀵 정렬은 다음과 같은 과정으로 정렬을 진행한다. 정렬은 오름차순으로 진행한다고 가정하자.

1. 주어진 배열에서 하나의 요소를 선택하고 이를 pivot(피벗) 으로 삼는다.
2. 배열 내부의 모든 값을 검사하면서 피벗 값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치한다.
3. 이렇게 하면 배열이 두 부분으로 나뉜다. 나뉜 이 두 개의 배열에서 각각 새로운 피벗을 만들어서 두개의 배열로 다시 쪼개어 준다.
4. 더 이상 배열을 쪼갤 수 없을 때까지 진행한다.

이 과정은 분할 정복의 원리를 이용한 것이다. 피벗을 중심으로 문제를 분할 하고, 피벗을 기준으로 해서 작은 값과 큰 값을 나열하는 정복 과정을 거친 뒤, 모든 결과를 결합 해서 큰 전체 문제를 해결한다.

Pivot Selection

퀵정렬에서 가장 핵심이 되는 부분은 어떻게 pivot을 선정하는지에 대한 부분이다. 퀵정렬의 최악의 경우의 시간복잡도는 O(N2) 이고 평균 복잡도는 𝛩(NlogN) 이기 때문에 피벗값을 잘못 선정하면 버블소트나 다름없는 성능을 보여준다.

피벗에 따라 시간복잡도가 극과극인 이유는 피봇을 통해 나누는 배열의 위치 때문이다. 만약 이미 정렬된 배열이나 역순으로 정렬된 배열이 있다고 하자. 이때 가장 처음값을 피벗으로 삼게되면 퀵소트 과정은 다음과 같이 진행된다.

1. | 1 | 2 | 3 | 4 | 5 | 이런 배열이 있을때, 1을 피벗으로 선택하게 되면,
2. 1을 기준으로 1보다 작은 값은 모두 왼쪽에 두고 큰 값은 모두 오른쪽에 두어야 하는데, 1보다 작은 값은 없기 때문에, 5부터 2까지 내려오면서 1과 비교하는 연산이 n-1번 수행된다.
3. 첫 분할이 끝나고 나면 다음 피벗은 2로 지정이 될텐데 이 때 역시 비교하는 연산이 n-1번 수행된다.
4. 따라서 피벗이 n에 도달할때까지 비교연산이 계속 진행되기 때문에 시간 복잡도는 n-1 * n 이 되어서 O(N^2) 가 되게된다.

반면에 배열이 정확하게 혹은 거의 근사하게 반으로 계속 나뉘어진다면 배열의 요소 갯수로 만들어지는 완전이진트리의 높이인 log n 에 대해 비교연산이 n번 수행되므로 시간 복잡도는 𝛩(nlogn) 이 된다.

이런 문제점에도 불구하고 퀵소트가 여전히 빠른 알고리즘으로 인정받는 이유는 완전히 정렬된 배열에 대해 퀵정렬을 수행할 가능성이 매우 적기 때문이다.

 

실행과정의 예시를 보자

 

 

 

 

 

 

 

 

 

 

이 과정을 한마디로 정리하면 pivot보다 큰 값을 pivot오른쪽에 놓기, pivot보다 작은 값을 왼쪽에 놓기와 동일하다고 

생각한다. 

 

따라서 pivot보다 작은 값의 list를 left 리스트, pivot보다 큰 값의 list를 right 리스트라고 두고

return을 할때 quick_sort(left) + [pivot] + quick_sort(right) 의 방식을 쓰면 더욱 간단하게 구현할 수 있다. 

 

 

 

구현 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    left = [x for x in arr[1:] if pivot > x]
    right = [x for x in arr[1:] if pivot <= x]

    return quick_sort(left) + [pivot] + quick_sort(right)

nums = [5, 3, 8, 4, 2, 7, 1, 10]
sorted_nums = quick_sort(nums)
print(sorted_nums)  # [1, 2, 3, 4, 5, 7, 8, 10]