퀵 정렬(Quick sort)
컴퓨터 언어에는 대부분 배열을 정렬하는 내장 정렬 함수가 있는데, 대다수가 내부적으로는 퀵 정렬 방법을 택하고 있다. 그 만큼 퀵정렬이 빠르기 때문이다. 퀵 정렬은 최악의 경우에는 삽입정렬이나 선택정렬 만큼 느리지만 대부분의 경우인 평균 시나리오에서는 훨씬 빠르다.
퀵 정렬은 분할(partition) 에 기반하고 있으며 이 분할이 재귀적으로 일어나는 과정을 통해 정렬된다.
분할
배열을 분할한다는 것은 피벗(기준 원소)를 기준으로, 피벗의 왼쪽에는 피벗보다 작은 수를 두고, 피벗의 오른쪽에는 피벗보다 큰 수를 두는 것을 말한다.
[0,5,2,1,6,3]이라는 배열을 가정하자.- 피벗을 정렬되지 않은 배열의 가장 오른쪽 원소라고 정하자. 그러면 맨 오른쪽 위치의
3이 피벗이 된다. - 분할의 목적은 피벗인 3의 왼쪽에는 피벗보다 작은 수를, 오른쪽에는 피벗보다 큰 수를 두는 것이다. 이 분할이 한 번 끝나면 적어도 피벗인 3은 올바른 위치에 정렬하게 된다. 한 번 분할이 끝나고 3이 올바른 위치에 정렬하면, 양 옆의 원소들 또한 재귀적으로 분할을 진행하며 피벗을 올바른 위치에 정렬한다.
- 기저 조건(base case)
*인 원소가 하나 남을 때까지 재귀적으로 진행되면 퀵 정렬이 완료된다.
* 기저 조건이란 중단 조건이라고도 한다. 재귀란 함수가 자기 자신을 반복적으로 호출하는 것을 의미하는데, 어느 순간에 중단하지 않는다면 무한 호출이 일어나면서 스택오버플로우가 일어난다. 그러므로 호출을 중단시키는 조건이 필요한데, 이를 기저 조건 또는 중단 조건이라고 한다.
재귀적으로 정렬을 하는 알고리즘에서는 정렬한 원소가 단 하나 남았을 때가 기저 조건이 된다. 원소가 하나일 때에는 정렬할 필요가 없기 때문이다. 또는 계승(factorial) 함수에서는 1! 이 기저 조건이 된다. 1!은 재귀함수를 호출할 필요도 없이 1인 것을 알 수 있기 때문이다.
배열이 한 번 분할하는 과정을 표현하자면 이렇다.
partition함수는 전체 배열(arr), 정렬하고자 하는 범위의 시작 인덱스(start)와 끝 인덱스(end)를 패러미터로 받는다.- 그 다음 해당 범위에 대해서 분할을 진행한다. (=피벗을 올바른 위치에 위치하게 한다. 다만 피벗은 주어진 범위에서 가장 오른쪽에 위치한 원소로 한다)
- 올바른 위치에 정렬하게 된 피벗의 위치를 리턴한다.
그 다음 분할은 피벗을 제외(피벗은 이미 정렬되었으므로)한 양 옆의 범위의 배열에 대해서 재귀적으로 진행하면 된다. 즉 배열의 원소가 총 7개이고 0~6까지의 인덱스를 갖고 있으며, 첫 분할 결과 올바르게 정렬한 피벗의 위치가 인덱스 3이라면, 인덱스 0~2의 범위에 대해 분할을 또 진행하고, 마찬가지로 인덱스 4~6의 범위에 대해 또 분할을 진행한다. 각 분할은 또 다시 새롭게 정렬된 피벗의 위치를 리턴할 것이고, 또 양 옆의 범위에 대해서 분할을 하고 …
def swap(arr, p1, p2):
arr[p1], arr[p2] = arr[p2], arr[p1]
# 배열의 맨 오른쪽 원소를 피벗으로 설정하는 경우의 분할
# start와 end는 분할을 진행할 범위를 나타냄. 시작 인덱스와 끝 인덱스.
# left와 right는 각각 왼쪽 포인터와 오른쪽 포인터의 위치
def partition(arr, start, end):
left = start
right = end-1
pivot_position = end
pivot = arr[pivot_position]
while True:
# 왼쪽 포인터 이동
# 왼쪽 포인터가 가리키는 값이 pivot과 같거나 클 경우 stop
while arr[left] < pivot:
left += 1
# 오른쪽 포인터 이동
# 오른쪽 포인터가 가리키는 값이 pivot과 같거나 작을 경우 stop
while arr[right] > pivot:
right -= 1
# 왼쪽과 오른쪽 모두 포인터가 멈추었을 때
# 왼쪽 포인터가 오른쪽 포인터보다 왼쪽에 위치한다면 둘을 교환
if left < right:
swap(arr, left, right)
# 왼쪽 포인터가 오른쪽 포인터와 같은 위치에 있거나 더 오른쪽일 때 while문 탈출
else:
break
# 왼쪽 포인터가 가리키는 원소와 피벗을 교환
swap(arr, left, pivot_position)
# 정렬된 피벗의 위치를 리턴
new_pivot_position = left
return new_pivot_position
def quick_sort(arr, start, end):
# 정렬할 부분이 존재하는지 체크
pi = 0
if start < end:
pi = partition(arr, start, end)
else:
return
quick_sort(arr, 0, pi-1)
quick_sort(arr, pi+1, end)
quick_sort 함수는 기저조건을 포함하고 있다. 원소가 단 하나이거나, 원소가 존재하지 않는다면 분할을 할 필요가 없다. 더 이상 정렬이 필요하지 않기 때문이다. 그래서 start < end이면 분할을 진행하고, start = end여서 원소가 단 하나인 경우나, start > end여서 원소가 존재하지 않는 경우에는 분할을 더 이상 진행하지 않고 탈출한다.
이 기저조건이 없으면 무한 호출이 일어나므로 매우 중요한 부분이다.
다만 나는 기저조건을 쓰고도 실수로 인해 계속 recursion error 가 났는데 마지막 줄에서 quick_sort(arr, pi+1, len(arr)-1)로 쓴 것이 원인이었다. 처음엔 얼핏 맞다고 생각했는데 전혀 아니다. 퀵소트를 처음 호출했을 때나 맞지, 그 다음 호출부터는 이렇게 쓰면 쪼개진 범위가 제대로 들어가지 않는다. 예를 들어 쪼개진 범위가 0~6 범위에서 피벗 위치가 4이면, 그 다음은 0~3, 5~6이 들어간다. 그 다음 0~3 범위에서 분할을 진행한 결과 피벗 위치가 2이면 0~1, 3~3 이렇게 다시 분할을 진행해야 하는데 len(arr)-1은 고정으로 6이라는 값을 가지니까 0~1, 3~6이 들어가 버린다. 3~3이면 더 이상 분할이 진행되지 않고 끝나야 하는데 3~6으로 잘못들어가니 계속 분할이 일어나서 결국 recursion error가 일어난다.
퀵 정렬의 효율성
| 삽입 정렬(Insertion sort) | 퀵 정렬(Quick sort) | |
|---|---|---|
| 최선 | O(n) | O(n*logn) |
| 평균 | O(n^{2}) | O(n*logn) |
| 최악 | O(n^{2}) | O(n^{2}) |
퀵 정렬에서 최악의 경우는, 분할 결과마다 피벗이 맨 끝에 위치하는 경우다. 원소가 총 N개일 때 분할을 하면 일어나는 최소 비교 횟수는 N번이다. 교환은 분할 한 번에 최소 1번, 최대 N/2번까지 일어난다. 비교와 교환을 합해도 빅오표기법으로 하면 O(n)이다. 피벗이 매번 맨 끝에 위치하면 총 비교하는 횟수만 합해도 N + (N-1) + (N-2) + … + 2 단계가 걸린다. 이를 합하면 약 N^{2}/2 인데 빅오표기에서는 상수항을 무시하므로 O(n^{2}) 이다.
반면 피벗이 맨 끝에 위치하지 않고 중간 쯤 위치한다면 비교 횟수가 훨씬 줄어들게 된다. 만약 피벗이 늘 배열의 중간 쯤에 위치한다면, 분할할 때 마다 절반씩 쪼개서 또 분할하는 형태가 반복될 것이다. 즉 전체 길이가 N일 때 logN만큼 쪼개지는데, 쪼갤 때마다 총 길이인 N에 대해 분할을 진행하므로 O(N*logN ) 이 긍정적인 시나리오일 때 퀵 정렬의 속도이다.