퀵 정렬이란?
퀵 정렬도 분할 정복 알고리즘입니다. 2개의 문제로 분할합니다. 합병 정렬(Merge Sort) 같은 경우에는 2개의 문제로 분할할 때, 문제의 크기가 항상 같았지만, 퀵 정렬은 일정하지 않은 형태로 분할합니다.
퀵 정렬은 피봇(pivot)이라 부르는 배열의 원소를 기준으로 피봇보다 작은 값은 왼쪽으로, 피봇보다 큰 값은 오른쪽으로 위치하도록 분할합니다.
이 과정을 통해 분할된 왼쪽 배열과 오른쪽 배열에도 동일한 과정을 수행합니다. 이렇게 반복을 하다 보면 배열은 어느새 정렬이 되어 있을 겁니다.
여기서 주의할 점은 피봇(pivot)은 분할된 왼편이나 오른편 부분에 포함되지 않습니다.
그 이유는 피봇을 기준으로 왼편과 오른편의 분할 과정을 수행했다면, 피봇의 위치는 확정되었기 때문입니다.
예를 들어 아래와 같은 정렬되지 않은 배열과 피봇(pivot)으로 60을 선정했다고 생각해 봅시다.
| 30 | 80 | 90 | 70 | 50 | 20 | 60 | 10 | 40 |
위 배열을 피봇을 기준으로 분할하면,
아래와 같이 되고, 피봇인 60은 이제 저 위치로 확정됩니다.
| 20 | 40 | 10 | 30 | 50 | 60 | 70 | 90 | 80 |
정렬을 모두 끝낸 배열을 보면 60의 위치는 변함이 없는 것을 알 수 있습니다.
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
▶ 퀵 정렬 수도 코드
QuickSort(A, left, right)
입력: 배열 A[left] ~ A[right]
출력: 정렬된 배열 A[left] ~ A[right]
if(left < right){
피봇을 A[left] ~ A[right] 중에서 선택하고 ,피봇을 A[left]와 자리를 바꾼 후, 피봇과 배열의
각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p -1]로 옮기고, 피봇보다 큰 숫자들은
A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.
QuickSort(A, left, p - 1) //피봇보다 작은 그룹
QuickSort(A, p + 1, right) //피봇보다 큰 그룹
}
→ if(left < right): 배열 A의 가장 왼쪽 인덱스인 left보다 배열 A의 가장 오른쪽 인덱스인 right가 클 경우에만 그 밑부분을 실행합니다. left < right 가 false인 경우는 바로 left = right인데, 이때는 더이상 분할할 수 없는, 원소가 1개라는 뜻이라 밑부분을 실행할 필요 없이 바로 return합니다.
→ 피봇 기준으로 분할: A[left] ~ A[right}에서 피봇을 선택하고, 피봇을 A[left]와 자리를 바꿉니다.(피봇 값은 A[left]에 존재) 그 후에 피봇 값과 A[left + 1] ~ A[right]의 값을 비교하며 피봇을 기준으로 위치를 바꿔줍니다. A[left + 1] ~ A[p -1] 에 피봇보다 작은 값, A[p + 1] ~ A[right]에는 피봇보다 큰 값으로 분할했다면, 피봇을 A[p]의 위치로 이동합니다.
(p는 피봇이 위치하게 되는 배열A의 인덱스)
→ 분할 후: 피봇을 기준으로 분할 과정을 끝마쳤다면, 피봇보다 작은 그룹과 피봇보다 큰 그룹으로 또 QuickSort 과정(위의 과정)을 각각 수행합니다.
▶ 퀵 정렬의 수행 과정
수행과정을 한 번 살펴보겠습니다. 피봇은 A[6]인 8로 선정을 하고, A[left]의 위치로 이동합니다.
왼쪽 인덱스 + 1(맨 왼쪽 데이터는 피봇이므로)부터 증가하는 변수를 low, 오른쪽 인덱스부터 감소하는 변수를 high로 지정합니다.
low는 계속 증가하다가 피봇 값보다 큰 값, 즉 왼쪽 그룹에 있어서는 안될 값을 만나면 멈춥니다.
high는 계속 감소하다가 피봇 값보다 작은 값, 즉 오른쪽 그룹에 있어서는 안될 값을 만나면 멈춥니다.
low < high 라면, A[low]와 A[high]의 값을 swap합니다.
위 과정을 low >= high 가 될 때까지 반복합니다.
반복이 끝나면, A[left]에 있던 피봇값와 A[high]의 값과 위치를 바꿉니다.즉, A[high]가 이제 피봇의 위치로 정해진 것입니다.
따라서 피봇의 왼쪽 그룹과 오른쪽 그룹의 함수 호출은
QuickSort(A, left, high - 1) = QuickSort(A, 0, 3) - 왼쪽
QuickSort(A, high + 1, right) = QuickSort(A, 5, 11) - 오른쪽
이렇게 하면 됩니다.
피봇의 왼쪽 그룹 함수 호출인 QuickSort(A, 0, 3) 과정을 살펴봅시다.
피봇을 A[3]인 6으로 선택했습니다. 위에서 설명한 과정을 통해 피봇을 기준으로 왼쪽과 오른쪽을 분할하고,
QuickSort(A, left, high - 1) = QuickSort(A, 0, 1) - 왼쪽
QuickSort(A, high + 1, right) = QuickSort(A, 3, 3) - 오른쪽
을 호출합니다.
오른쪽 그룹의 QuickSort함수는 left < right 의 조건이 성립하지 않아서 바로 return 됩니다.
왼쪽 그룹의 QuickSort 호출인 QuickSort(A, 0, 1)을 살펴봅시다.
피봇은 A[1]인 3이 선택되었습니다.
여기서는 변수 low와 high가 low = 1, high = 1로 초기화됩니다. 분할 과정이 끝난 후 함수 호출은
QuickSort(A, left, high - 1) = QuickSort(A, 0, 0) - 왼쪽
QuickSort(A, high + 1, right) = QuickSort(A, 2, 1) - 오른쪽
왼쪽 그룹 함수와 오른쪽 그룹 함수의 호출은 left < right의 조건을 둘 다 만족시키지 못하므로 호출이 되지 않습니다.
따라서 여기까지의 과정이 QuickSort(A, 0, 3)의 과정이었습니다.
현재 상태를 살펴보면, 아래와 같습니다.
QuickSort(A, 0, 11)의 호출에서 피봇이었던 8의 왼쪽 그룹이 정렬된 것을 알 수 있습니다.
여태까지 살펴본 과정을 오른쪽 그룹도 수행하면, 정렬된 전체 정렬을 만날 수 있습니다.
▶ 퀵 정렬의 파이썬 코드
def partition(start, end, array):
pivot_index = start
pivot = array[pivot_index]
while start < end:
while start < len(array) and array[start] <= pivot:
start += 1
while array[end] > pivot:
end -= 1
if(start < end):
array[start], array[end] = array[end], array[start]
array[end], array[pivot_index] = array[pivot_index], array[end]
return end
def quick_sort(start, end, array):
if (start < end):
p = partition(start, end, array)
quick_sort(start, p - 1, array)
quick_sort(p + 1, end, array)
array = [ 10, 7, 8, 9, 1, 5 ]
quick_sort(0, len(array) - 1, array)
print(f'Sorted array: {array}')
먼저, partition(start, end, array) 함수부터 봅시다.
피봇을 배열의 첫 번째 원소로 지정합니다. (pivot_index = start)
start는 배열의 맨 왼쪽 인덱스, end는 배열의 맨 오른쪽 인덱스를 가리킵니다. while문(start< end)을 돌면서
start가 배열의 길이보다 커지거나, array[start]의 값이 피봇보다 커질 때까지 start를 증가시키고,
array[end] 값이 피봇보다 작을 때까지 end를 감소시킵니다.
while문을 빠져나오게 되면, end의 원소의 피봇의 값의 위치를 바꿉니다.
pivot의 위치가 확정되었습니다.
def partition(start, end, array):
pivot_index = start
pivot = array[pivot_index]
while start < end:
while start < len(array) and array[start] <= pivot:
start += 1
while array[end] > pivot:
end -= 1
if(start < end):
array[start], array[end] = array[end], array[start]
array[end], array[pivot_index] = array[pivot_index], array[end]
return end
함수 quick_sort(start, end, array) 는 partition함수를 왼쪽과 오른쪽 배열 둘 다 호출될 수 있게 만들어줍니다.
원소의 개수가 2개 이상이라면, p = partition(start, end, array)를 통해 pivot의 위치를 p로 받고,
피봇의 왼쪽 배열 quick_sort를 호출하고, 피봇의 오른쪽 배열 quick_sort를 호출합니다.
def quick_sort(start, end, array):
if (start < end):
p = partition(start, end, array)
quick_sort(start, p - 1, array)
quick_sort(p + 1, end, array)
▶ 퀵 정렬의 시간복잡도
- 최악의 경우
퀵 정렬의 성능은 피봇 선택이 좌우합니다. 피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되면, 한 부분으로 치우치는 분할이 발생합니다.
예를 들어 피봇으로 가장 작은 숫자가 선택되었을 경우를 보면, 아래와 같습니다.
이때 피봇 선택 방법은 알 수 없지만, 매번 가장 작은 숫자를 선택했습니다.
비교 횟수를 보면,
피봇 = 1일 때: 8회 - [17, 42, 9, 18, 23, 31, 11, 26]과 각각 1회씩 비교
피봇 = 9일 때: 7회 - [42, 17, 18, 23, 31, 11, 26]과 각각 1회씩 비교
피봇 = 11일 때: 6회 - [17, 18, 23, 31, 42, 26]과 각각 1회씩 비교
피봇 = 17일 때: 5회 - [18, 23, 31, 42, 26]과 각각 1회씩 비교
.....
피봇 = 31일 때: 1회 - [42]와 1회 비교
감이 잡히셨죠?
만일 입력의 크기가 n이라면, 최악 경우 시간복잡도는 (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2
즉, O(n^2)입니다.
- 최선의 경우
따라서 최대한 반으로 나눌 수 있는 피봇을 찾는 게 효율적인 알고리즘을 작성하는 데 유리합니다.
즉, 최선의 경우는 반으로 정확히 나누는 피봇을 매번 선택할 때인데, 이때의 시간복잡도는
O(nlogn)입니다.
각 층에서는 각각의 원소가 각 부분의 피봇과 1회씩 비교됩니다. 따라서 비교 횟수는 O(n) 이고, 그러므로 총 비교 횟수는 O(n) x (층수) = O(n) x log2(n)
(층수가 log2(n)인 이유는 n/2^k = 1 일 때 k = log2(n)이기 때문입니다.) 이때 2는 로그의 밑입니다.
- 평균 경우
피봇을 항상 랜덤하게 선택한다고 가정하면, 퀵 정렬의 평균 시간 복잡도를 계산할 수 있습니다.
최선 경우와 동일한 O(nlogn)입니다. (최선의 경우와 약간의 상수차이는 있습니다.)
▶ 퀵 정렬의 피봇 선정 방법
1) 랜덤하게 선정하는 방법
2) 3개의 숫자의 중앙값으로 선정하는 방법(Median of Three)
→ 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값으로 피봇을 정합니다.
예를 들어, [31, 1, 26] 중에서 중앙값인 26을 피봇으로 사용하는 것입니다.
| 31 | .... | 1 | ... | 26 |
3) (Median-of-Medians)
→ 배열을 3등분한 후, 각 부분에서 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값으로 피봇을 정합니다.
입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해서, 삽입 정렬을 동시에 사용합니다.
→ 입력의 크기가 작을 때에는 퀵 정렬이 삽입 정렬보다 빠르지만은 않습니다. (퀵 정렬은 순환 호출로 수행되기 때문)
따라서, 부분 문제의 크기가 작아지면, 더 이상의 분할(순환 호출)을 중단하고 삽입 정렬을 사용합니다.
▶ 퀵 정렬의 적용
- 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 알고리즘
- 실질적으로 어느 정렬 알고리즘보다 좋은 성능
- 생물 정보 공학(Bioinformatics)에서 특정 유전자를 효율적으로 접미 배열과 함께 활용
오타나 오류 지적 언제든 환영입니다. :)
참고: 알기 쉬운 알고리즘(양성봉)
'Algorithm > Divide-and-Conquer' 카테고리의 다른 글
| [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 (0) | 2021.10.21 |
|---|---|
| [ 알고리즘 공부 ] 선택 문제 알고리즘(Selection) (feat.python 파이썬) (0) | 2021.10.07 |
| [ 알고리즘 공부 ] 합병 정렬(Merge Sort) 알고리즘 - 분할 정복 알고리즘(python, 파이썬) (2) | 2021.10.01 |
