[Algorithm] Quick Sort (퀵 정렬)

0. Quick Sort (퀵 정렬) 이란?

 

기준 (pivot)을 잡아 pivot보다 큰 원소는 뒤에, 작은 원소는 앞에 놓으면서 정렬하는 것이다. 마지막엔 가운데에 pivot을 넣어준다.

그러나 pivot보다 작은 원소, 큰 원소끼리는 정렬되어 있지 않을 것이다.

즉, pivot의 왼쪽, 오른쪽에 대해 다시 정렬을 수행해야 한다는 것이다. 따라서 이도 재귀를 이용한다.

 

[1, 4, 3, 5, 2] 를 맨 오른쪽 원소를 pivot으로 삼아 정렬한다고 하자.

한 번의 pivot을 기준으로 한 분할을 이용하면 다음과 같은 결과가 출력될 것이다. 

[1, 2, 4, 3, 5]

2의 왼쪽에는 1 하나뿐이므로 더 이상 정렬할 필요가 없다. 따라서 우리는 [4, 3, 5]를 정렬해야 한다.

마찬가지로 가장 오른쪽 원소인 5를 기준으로 정렬을 하면, 4, 3은 모두 5보다 작기 때문에 배열에 변화가 없을 것이다. 

이 때 5는 이미 pivot이 되었던 전적이 있으므로, 정렬 대상에 포함시키지 않는다.

제일 크니까 맨 오른쪽에 있을 것이고, 그것을 다시 기준 삼을 필요는 없다.

따라서 남은 4, 3중에 왼쪽인 3을 기준으로 정렬하면 3, 4가 될 것이다. 정렬되지 않은 원소는 3 하나만 남아있기 때문에 종료한다.

[1, 2, 3, 4, 5]

 

5를 pivot으로 잡는 게 불필요해 보일 수 있다. 정확하다.

따라서 pivot을 제대로 잡아주는 알고리즘이 필요한데 이는 연구되고 있고, 실제 상황에서는 맨 왼쪽 혹은 오른쪽을 pivot으로 잡는 것이 일반적이다.

 

1. 구현

 

n = int(input())
nums = input()
num = nums.split()

for i in range(n):
    num[i] = (int)(num[i])

def swap(num, i, j):
    tmp = num[j]
    num[j] = num[i]
    num[i] = tmp

    return num

def partition(num, low, high):
    pivot = num[high]
    i = low - 1
    for j in range(low, high):
        if num[j] < pivot:
            i += 1
            swap(num, i, j)
    swap(num, i + 1, high)
    return i + 1

def quick_sort(num, low, high):
    if low < high:
        pos = partition(num, low, high)

        quick_sort(num, low, pos-1)
        quick_sort(num, pos+1, high)

    return num

num = quick_sort(num, 0, n-1)

for i in range(n):
    print(num[i], end=' ')

1) swap

python의 교환 기능을 잘 알고 있다면 굳이 구현할 필요 없다. 두 원소를 바꿈을 강조하기 위해 구현했다.

 

2) partition

pivot을 기준으로 둘을 나눴다면, 나눠진 곳의 index가 필요할 것이다. 그래야 그 index를 기준으로 왼쪽, 오른쪽을 다시 정렬할 수 있기 때문이다. 따라서 position (코드 내에선 pos 변수)를 찾아주는 기능을 하는 함수를 구현한다.

i를 low-1로 설정한 이유는, 맨 첫번째 원소가 pivot보다 작은 경우 pivot이 들어갈 위치를 뒤로 옮기면서 바꾸어주어야 하기 때문이다.

pivot보다 작은 원소를 for문을 통해 전부 앞으로 보내며 작을 때마다 index를 더하면 index는 왼쪽의 마지막 위치를 가리킬 것이다. 따라서 pivot이 들어갈 위치 pos는 i+1을 반환한다.

 

3) quick_sort

이제 pivot을 기준으로 왼쪽, 오른쪽을 정렬하는 과정을 재귀적으로 반복한다. low < high 조건문이 없으면 무한루프가 된다.

 

4) quick_sort(num, 0, n-1) 

코드 내에서 high를 포함하여 진행하므로 실제 마지막 index인 n-1을 high로 둔다.