퀵 정렬

퀵 정렬

퀵 정렬은 분할정복법(divide & conquer) 알고리즘으로 일반적으로 $O(n\log_2 n)$의 시간복잡도를 가지고, 최악의 상황(모두 정렬된 상태)에서 $O(n^2)$의 시간복잡도를 가집니다.

퀵 정렬에서는 Pivot과 Low, High 라는 포인터를 사용하여 정렬합니다. 이때, Pivot 값을 기준으로 왼쪽에 Pivot 값보다 작은 요소들이 오고, 오른쪽에 Pivot 값보다 큰 요소들이 오게 됩니다. Pivot은 일반적으로 부분 배열에서 가장 첫번째 값으로 합니다.

인덱스	1	2	3	4	5	6	7	8	9
값	5	3	8	4	9	1	6	2	7
포인터	Pivot, Low								High

위와 같은 배열이 있다고 했을 때, 퀵 정렬의 수행 과정은 다음과 같습니다.

먼저 Pivot은 5, Low는 인덱스 1번, High 인덱스 9번입니다. Low 포인터는 Low + 1 번째 값이 Pivot보다 클 때까지 + 1 을 해주고, High 포인터는 High - 1 번째 값이 Pivot보다 작을 때까지 - 1 을 해줍니다. 그리고 만약 Low 가 High 보다 작다면, High와 Low를 교체해줍니다. 그리고 이 과정을 반복합니다.

여기서 교체를 해준다는 것은, 왼쪽에는 Pivot보다 작은 값만 와야하는데, 큰 값이 있으므로 오른쪽의 작은 원소와 서로 바꿔준다는 것입니다.

Low와 High 값이 교차될 때, Pivot과 High를 교체합니다. 이 과정을 거치면 왼쪽에 Pivot 보다 작은 값이, 오른 쪽에는 Pivot 보다 큰 값이 오게 됩니다. 이 과정을 배열의 크기가 1이 될 때까지 반복합니다.

교차되었다는 것은 각각의 원소가 알맞은 위치, 즉 Pivot을 기준으로 왼쪽에는 작은 원소만, 오른쪽에는 큰 원소만 있다는 뜻입니다.

Step #1

인덱스	1	2	3	4	5	6	7	8	9
값	5	3	8	4	9	1	6	2	7
포인터	Pivot		Low					High

이때 Low < High 이므로, 서로 교체합니다.

인덱스	1	2	3	4	5	6	7	8	9
값	5	3	2	4	9	1	6	8	7
포인터	Pivot		Low					High

Step #2

인덱스	1	2	3	4	5	6	7	8	9
값	5	3	2	4	9	1	6	8	7
포인터	Pivot				Low	High

인덱스	1	2	3	4	5	6	7	8	9
값	5	3	2	4	1	9	6	8	7
포인터	Pivot				Low	High

Step #3

인덱스	1	2	3	4	5	6	7	8	9
값	5	3	2	4	1	9	6	8	7
포인터	Pivot				High	Low

이때 High와 Low가 교차되었으므로, High와 Pivot을 교체합니다.

인덱스	1	2	3	4	5	6	7	8	9
값	1	3	2	4	5	9	6	8	7
포인터	Pivot				High	low

5번 인덱스인 5를 기준으로 왼쪽에는 더 작은 값들이, 오른쪽에는 더 큰 값들이 온 것을 확인할 수 있습니다. 이제 인덱스 5를 기준으로 나눠서 왼쪽을 퀵 정렬로 정렬하고, 오른쪽을 퀵 정렬로 정렬합니다.

Step #4

인덱스	1	2	3	4	5	6	7	8	9
값	1	3	2	4	5	9	6	8	7
포인터	Pivot, Low			High		Pivot, Low			High

인덱스	1	2	3	4	5	6	7	8	9
값	1	3	2	4	5	9	6	8	7
포인터	Pivot, High	Low				Pivot, Low			High

이때, High < Low 이므로, Pivot과 High를 교체합니다.

인덱스	1	2	3	4	5	6	7	8	9
값	1	3	2	4	5	9	6	8	7
포인터	Pivot, High	Low				Pivot, Low			High

Step #5

이제 인덱스 1을 기준으로 왼쪽에는 1보다 작은 값(아무 값도 없음), 오른쪽에는 더 큰 값이 온 것을 확인할 수 있습니다. 인덱스 1을 기준으로 오른쪽을 퀵 정렬합니다.

인덱스	1	2	3	4	5	6	7	8	9
값	1	3	2	4	5	9	6	8	7
포인터		Pivot, Low		High		Pivot, Low			High

인덱스	1	2	3	4	5	6	7	8	9
값	1	3	2	4	5	9	6	8	7
포인터		Pivot	High	Low		Pivot, Low			High

이때 High < Low 이므로, Pivot과 High를 교체해줍니다.

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	9	6	8	7
포인터		Pivot	High	Low		Pivot, Low			High

3번째 인덱스를 기준으로, 오른쪽은 3번째 인덱스인 3보다 큰 값, 왼쪽은 3보다 작은 값이 온걸 확인할 수 있습니다. 이때 왼쪽과 오른쪽의 크기가 1이므로, 퀵 정렬을 수행하지 않습니다.

Step #6

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	9	6	8	7
포인터						Pivot, Low			High

이제 남은 오른쪽 부분을 퀵 정렬하면,

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	9	6	8	7
포인터						Pivot			High, Low

이때 High > Low가 아니므로, Pivot과 High를 교체합니다.

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	7	6	8	9
포인터						Pivot			High, Low

이제 인덱스 9를 기준으로 왼쪽을 정렬합니다.

Step #7

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	7	6	8	9
포인터						Pivot, Low		High

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	7	6	8	9
포인터						Pivot	High	Low

이때 High < Low 이므로, Pivot과 High를 교체해줍니다.

인덱스	1	2	3	4	5	6	7	8	9
값	1	2	3	4	5	6	7	8	9
포인터						Pivot	High	Low

이때 인덱스 7번을 기준으로 양옆의 배열의 크기가 1이므로, 더이상 퀵정렬을 수행하지 않습니다

파이썬 코드

import sys

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

def quicksort(arr, start, end):
    if start < end:
        index = partition(arr, start, end)
        quicksort(arr, start, index - 1)
        quicksort(arr, index + 1, end)

arr = [0, 8, 2, 9, 3, 1, 4, 5]
quicksort(arr, 0, len(arr) - 1)
print(*arr)