퀵 정렬은 일반적으로 폭넓게 사용되는 아주 빠른 정렬 알고리즘입니다.
퀵 정렬 살펴보기
다음은 학생수가 8명인 그룹을 키순으로 정렬하는 모습을 나타냈습니다.
한 사림의 키를 선택하여 그 학생을 기준으로 큰 사람의 그룹과 작은 사람의 그룹으로 나눕니다. 이 때 학생 A를 피벗이라고 하며, 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마칩니다.
배열을 두 그룹으로 나누기
먼저 배열을 두 그룹을 나누는 순서입니다.
다음 배열에서 피벗으로 6을 선택하여 나누고 피벗을 x, 왼쪽 끝 요소 pl을 왼쪽 커서, 오른쪽 끝 요소 pr을 오른쪽 커서라고 하겠습니다.
| pl | x | pr | ||||||
|---|---|---|---|---|---|---|---|---|
| 5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 하므로 다음 작업을 수행합니다.
- a\ [pl] >= x 가 성립하는 요소를 찾을 때 까지 pl을 오른쪽으로 스캔
- a\ [pr] ⇐ x 가 성립하는 요소를 찾을 때 까지 pr을 왼쪽으로 스캔
이 과정을 거치면 pl과 pr은 다음 위치에서 멈추게 됩니다. 여기서 왼쪽과 오른쪽 커서가 가리키는 두 요소의 값을 교환합니다.
| pl | x | pr | ||||||
|---|---|---|---|---|---|---|---|---|
| 5 | 7 | 1 | 4 | 6 | 2 | 3 | 9 | 8 |
다시 스캔을 계속하면 왼쪽과 오른쪽 커서는 다음 위치에서 멈춥니다. 이 두 요소의 값을 교환합니다.
| pl | pr | |||||||
|---|---|---|---|---|---|---|---|---|
| 5 | 3 | 1 | 4 | 6 | 2 | 7 | 9 | 8 |
다시 스캔을 하면 두 커서가 교차합니다.
| pr | pl | |||||||
|---|---|---|---|---|---|---|---|---|
| 5 | 3 | 1 | 4 | 2 | 6 | 7 | 9 | 8 |
두 커서가 교차하면 그룹을 나누는 과정이 끝나고 배열은 다음처럼 두 그룹으로 나뉩니다.
- 피벗 이하의 그룹 : a[0] , … , a[pl-1]
- 피벗 이상의 그룹 : a[pr+1] , … , a[n-1]
또한 그룹을 나눈 다음 pl> pr+1 이면 다음과 같은 그룹이 생깁니다.
- 피벗과 같은 값을 갖는 그룹 : a[pr+1] , … , a[pl-1]
다음은 피벗이 5일 경우 피벗과 같은 값을 같는 그룹이 만들어지는 예시입니다.
다음은 위의 내용을 바탕으로 구현된 배열을 나누는 프로그램입니다.:
//--- 배열 요소 a[idx1]과 a[idx2]의 값을 교환 ---//
static void swap(int[] a, int idx1, int idx2) {
int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t;
}
//--- 배열을 나눔 ---//
static void partition(int[] a, int n) {
int pl = 0; // 왼쪽 커서
int pr = n - 1; // 오른쪽 커서
int x = a[n / 2]; // 피벗(가운데 요소)
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr)
swap(a, pl++, pr--);
} while (pl <= pr);
System.out.println("피벗의 값은 " + x + "입니다.");
System.out.println("피벗 이하 그룹 ");
for (int i = 0; i <= pl - 1; i++) // a[0] ～ a[pl - 1]
System.out.print(a[i] + " ");
System.out.println();
if (pl > pr + 1) {
System.out.println("피벗과 일치하는 그룹 ");
for (int i = pr + 1; i <= pl - 1; i++) // a[pr + 1] ～ a[pl - 1]
System.out.print(a[i] + " ");
System.out.println();
}
System.out.println("피벗 이상 그룹 ");
for (int i = pr + 1; i < n; i++) // a[pr + 1] ～ a[n - 1]
System.out.print(a[i] + " ");
System.out.println();
}