퀵 정렬 (Quick sort)

pivot은 중간지점을 가리킨다.

퀵 정렬이란?

Quick sort는 Divide and Conquer 알고리즘으로, 평균적으로 매우 빠른 수행 속도를 보여준다. 시간복잡도가 O(NlogN)으로 Merge sort와 동일하지만, 배열을 균등하지 않게 분할하고 추가적인 메모리 공간을 필요로 하지 않는다. 빠르고 메모리도 덜 차지하지만 pivot을 잘못 설정했을 경우, 최악의 경우에는 시간복잡도가 O(N^2)으로 다른 비효율적인 정렬 알고리즘보다 나은 것이 없다.  그래서 pivot의 위치에 큰 영향을 받지 않는 배열에 적합하다.

pivot은 배열을 분할하는 기준점으로, pivot으로 나눠진 두 배열의 원소를 순서대로 꺼내 비교하면서 정렬한다. 

 

 

원리

배열을 정렬하려면 먼저 3가지 변수를 설정해 두어야 한다.

left: 배열 맨 왼쪽 인덱스. 밑줄로 표시

pivot: 배열 맨 오른쪽 인덱스. 볼드로 표시

right: 배열 맨 오른쪽 인덱스. 이탤릭체로 표시

 

Quick sort는 다음과 같은 연산을 수행한다.

1. left 위치의 값이 pivot 위치의 값보다 커질 때까지 인덱스를 증가시킨다.

2. right 위치의 값이 pivot 위치의 값보다 작아질 때까지 인덱스를 감소시킨다.

3. left 값이 pivot 값보다 크고, right 값이 pivot 값보다 작으면 left와 right 값을 교환한다.

4. left 인덱스값이 right인덱스값보다 커지면, left와 pivot을 교환한다.

5. pivot을 기준으로 배열을 두 개로 나눠 각각의 연산을 수행한다.

6. 이 과정은 더이상 배열을 나눌 수 없을 때까지 반복한다.

 

이 방법으로 [5, 1, 4, 2, 3]을 오름차순으로 정렬해 보자.

1. [5, 1, 4, 2, 3] : pivot은 배열 맨 오른쪽으로 잡고, left와 right를 교환 조건에 해당될 때까지 옮긴다.

2. [5, 1, 4, 2, 3] : pivot 값보다 left값이 크고 right 값이 작으므로 교환한다.

3. [2, 1, 4, 5, 3] : left와 right를 교환 조건에 해당될 때까지 옮긴다.

4. [2, 1, 4, 5, 3] : left 인덱스가 right 인덱스보다 커졌으니 left와 pivot을 교환한다.

5. [2, 1, 3, 5, 4] : pivot을 기준으로 배열을 나눈다.

6. [2, 1] [3] [5, 4]

6-1. [2, 1] : pivot은 배열 맨 오른쪽으로 잡고, left와 right를 교환 조건에 해당될 때까지 옮긴다.

6-1. [2, 1] : left 인덱스가 right 인덱스와 같아졌으니 pivot과 left를 교환한다.

6-1. [1, 2] : pivot을 기준으로 배열을 나누면 더 이상 나눌 수 없는 원자값이 된다. 정렬 결과를 리턴한다.

6-2. [3] : 더 이상 나눌 수 없는 값이다.

6-3. [5, 4] : 6-1과 같은 연산을 한다.

6-3. [4, 5] : pivot을 기준으로 배열을 나누면 더 이상 나눌 수 없는 원자값이 된다. 정렬 결과를 리턴한다.

7. [1, 2] [3] [4, 5] : 정렬되었다.

 

 

구현

Quick sort는 Merge sort와 마찬가지로 재귀를 사용하면 쉽게 풀 수 있다.

 

Python - Recursive

- pivot을 중간값으로 정했다.

- less, more 캐시값을 설정해 pivot보다 작은 값은 less에, 큰 값은 more에 넣는다.

- 다 넣으면 less, more 배열에 정렬을 재귀적으로 수행한다.

def solution2(n, arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) //2]
    less = []
    more = []
    equal = []
    for a in arr:
        if a< pivot:
            less.append(a)
        elif a> pivot:
            more.append(a)
        else:
            equal.append(a)
        print(less, more, equal)
    return solution2(n, less) + equal + solution2(n, more)

- 추가 배열을 사용하지 않고도 구현할 수 있다. 

 

# quick sort -non recursive
def solution3(arr):
    if len(arr) <= 1:
        return arr
    pivot = len(arr)-1
    left = 0
    right = len(arr)-1

    while True:
        while arr[left] < arr[pivot]:
            left+=1
        while arr[right] > arr[pivot]:
            right-=1
        if left >= right:
            break
        arr[right], arr[left] = arr[left], arr[right]
    arr[left], arr[pivot] = arr[pivot], arr[left]
    print(arr)
    return solution3(arr[:pivot]) + [arr[pivot]] + solution3(arr[pivot+1:])