[알고리즘] 퀵 정렬 (Quick Sort) 이란?

퀵 정렬 (Quick Sort) 란?

재귀를 활용한 분할 정복 알고리즘.

특정 위치에 있는 원소를 pivot이라고 할 때 pivot을 기준으로 pivot보다 작으면 왼쪽, pivot보다 크면 오른쪽으로 이동하는 알고리즘이다.

 

 

과정

1. pivot을 선택한다.

2. pivot 값보다 작은 값들은 모두 왼편으로 몰고, 큰 값들은 모두 오른편으로 몰아놓는다. 이후에는 왼편과 오른편에 있는 값은 항상 오른편의 값이 크므로 서로 비교를 할 필요가 없다.

3. 왼편과 오른편에 있는 배열에서 1, 2번의 과정을 반복하며, (왼편 또는 오른편)으로 이동하는 값들이 모두 1개인 경우 해당 배열을 반환한다.

 

예시

# 초기 배열
[6, 5, 1, 4, 7, 2, 3]

# pivot을 가운데 값으로 선택하여 2번을 수행
            p
[3, 2, 1] < 4 < [7, 5, 6]

# 왼편의 배열을 다시 같은 방법으로 수행
      p
[1] < 2 < [3]

# 오른편의 배열을 같은 방법으로 수행
     p
[] < 5 < [7, 6]

# 오른편의 오른편 배열을 같은 방법으로 수행
      p
[6] < 7 < []

# 마지막으로 지금까지 좌우로 분할했던 값들을 모두 합침
[1, 2, 3, 4, 5, 6, 7]

 

Python Code

def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)

sort()와 partition()의 2개의 함수로 나누어진다.

sort() 함수는 재귀 함수이며 정렬 범위를 시작 인덱스와 끝 인덱스로 인자를 받는다.

partition() 함수는 정렬 범위를 인자로 받으며 다음 로직을 따라 좌우측의 값들을 정렬하고 분할 기준점의 인덱스를 리턴한다.

 

시간 복잡도

- 퀵 정렬의 성능은 어떻게 pivot 값을 선택하느냐에 따라 크게 달라질 수 있다. 이상적인 경우, pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 병합 정렬과 마찬가지로 O(NlogN)의 시간 복잡도를 가지게 된다.

- 하지만 pivot 값을 기준으로 분할 했을 때 값들이 한 편으로 크게 치우치게 되면 성능이 저하되어 최악의 경우 한 편으로만 모든 값이 몰리게 되어 O(N^2)의 시간 복잡도를 보일 수 있다.

 

공간 복잡도

- 위 코드처럼 입력 배열이 차지하는 메모리만을 사용하는 in-place sorting 방식으로 구현을 사용할 경우 O(1)의 공간 복잡도를 가지게 된다.