QuickSort(1)-알고리즘03
퀵정렬
많은 정렬 알고리즘 중에 퀵정렬을 다뤄본다. 퀵정렬을 공부하다보면 얻게 되는 것이 많다.
Divide and Conquer(분할정복) , Pivot , Partition 에 대한 개념을 같이 공부하게 된다.
퀵 정렬은 다음과 같은 과정으로 정렬을 한다. (Input=array:ARR[0])
1. 배열의 원소중 하나를 골르는데 이를 pivot이라고 한다.
2. pivot보다 큰 값의 원소들은 pivot의 오른쪽으로, pivot보다 작은 원소들은 pivot의 왼쪽으로 자리를 옮긴다
(partition)
3. pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 분할을 해서 각각의 배열에 대해 1,2의 과정을 반복한다.
(Divide and Conquer)
pivot을 정하는 방법과 partition의 방법은 다양하다. 방법에 따라 Quick Sort의 time complexity가 다양하게 나타나기도 한다.
이 것들은 추후에 다루고 지금의 목표는 QuickSort 알고리즘의 과정을 이해하는 것이므로 pivot을 내 마음대로 설정한다고 하자.(항상 배열의 가장 왼쪽 원소를 pivot으로 설정하는 것이 일반적이다:ARR[0])
<1>
예를 들어보자. 여기서 임의의 원소(5라 하자)를 pivot으로 정한다
| 1 | 4 | 9 | 8 | 2 | 5 | 3 | 7 |
<2>
pivot(5)를 기준으로 2의 과정을 실행한다. 대부분 배열을 탐색할때 ARR[0]에서 부터 시작하므로 다음과 같은 순서의 결과가 나오게 된다.
| 1 | 4 | 2 | 3 | 5 | 9 | 8 | 7 |
<3>
5를 기준으로 좌,우 두개의 배열로 쪼개고 각 배열에 대하여 1~3의 과정을 더 이상 쪼갤 수 없을 때 까지 반복한다.
아래에서는 왼쪽에 있는 배열에 대해서는 pivot을 2로, 오른쪽은 pivot을 9로 선택했다.
| 1 | 2 | 4 | 3 | 5 | 8 | 7 | 9 |
계속 반복하다 보면 다음과 같이 정렬이 완료된다.
| 1 | 2 | 3 | 4 | 5 | 7 | 8 | 9 |
퀵정렬의 Pseudocode(의사코드)는 다음과 같다.
배열A에 대하여 1~3의 과정을 실행하는데, p 와 r은 배열을 분할할때 쓰인다.
p는 분할된 배열의 가장 왼쪽 index, r은 가장 오른쪽 index 를 의미하고 q는 pivot이다. q를 기준으로 partition(2의 과정)을 진행한다.
4번째 줄의 의미는, pivot을 기준으로 왼쪽의 배열에 대해 1~3의 과정을 반복.
5번째 줄의 의미는, pivot을 기준으로 오른쪽의 배열에 대해 1~3의 과정을 반복한다.
이를 해석하면, QuickSort의 시간복잡도는
T(n)= T(q) + T(n-q) + O(n)
이다.
퀵정렬 분석(Analysis of QuickSort)
이때 우리가 pivot을 어떻게 정하냐에 따라 T(n)이 O(nlogn) 이 될 수도 있고, O(n^2)이 될 수도 있다.
따라서 많은 사람들이 퀵정렬의 최악의 경우 시간복잡도는 O(n^2)이라고 알고 있으나 우리는 pivot을 정하는 어떤 method를 이용하여 최악의 경우에도 O(nlogn)의 시간에 정렬을 할 수 있는 퀵정렬을 만들 수 있다.
이 부분에 대하여 다음 포스팅에서 수식으로 증명을 하고자 한다.