퀵 정렬
- Quick Sort는 분할 정복 방법을 통해 주어진 배열을 정렬한다.
- 분할 정복 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
- Quick Sort는 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
- Merge Sort(병합 정렬)와는 달리 Quick Sort는 배열을 비균등하게 분할한다.
개념
- 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를
피벗(pivot) 이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.
- 이렇게 배열을 둘로 나누는 것을 분할(Divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로,
이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.- 배열에서 피벗으로 6을 선택하여 나눈다.
- 피벗을 x, 왼쪽 끝 요소의 인덱스 pl을 왼쪽 커서, 오른쪽 끝 요소의 인덱스 pr을 오른쪽 커서로 지정한다.
| pl |
|
|
|
x |
|
|
|
pr |
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| 5 |
7 |
1 |
4 |
6 |
2 |
3 |
9 |
8 |
- a[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다.
- a[pr] <= x 가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 스캔한다.
- 이 과정을 거치면 pl과 pr은 아래 테이블의 위치에서 멈춘다.
- 여기서 왼쪽과 오른쪽 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환한다.
- 그러면 피벗 이하의 값은 왼쪽으로, 피벗 이상의 값은 오른쪽으로 이동한다.
- 다시 스캔을 계속하면 왼쪽과 오른쪽 커서는 아래 테이블의 위치에 멈춘다.
- 이 두 요소 a[pl]과 a[pr]의 값을 교환한다.
- 다시 스캔을 계속하면 두 커서가 교차하게 된다.
- pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 두 그룹으로 나누어진다.
피벗 이하의 그룹: a[0], ... , a[pl - 1]
피벗 이하의 그룹: a[pr + 1], ... , a[n - 1]
- 그룹을 나누는 작업이 끝난 다음 pl > pr + 1 이면 피벗과 같은 값을 갖는 그룹이 생길 수 있다.
- a[pr + 1], ..., a[pl - 1]
- pl,pr이 동일한 인덱스에 있을 때도 요소를 교환하는데, 동일한 요소를 교환하는 시도가 의미 없어 보이지만
- 이 시도는 아무리 많아야 1회이므로 교환해도 괜찮다.
- 이런 시도를 줄이기 위해 같은 요소를 교환하지 않는다면 요소를 교환하기 전에 pl,pr이 동일한 요소 위에 있는지를 매번 검사해야 하고, 이 비용이 훨씬 크다.
재귀적인 퀵 정렬
static void quickSort(int[] a, int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
// partition - 배열 그룹 분리
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) swap(a, pl++, pr--);
} while (pl <= pr);
if (left < pr) quickSort(a, left, pr);
if (pl < right) quickSort(a, pl, right);
System.out.println(Arrays.toString(a));
}
Quick Sort 개선
- 정렬하고자 하는 배열이 오름차순 정렬되어있거나 내림차순 정렬되어있으면 O(n^2)의 시간 복잡도를 가진다.
- 이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도 O(nlog₂n)으로 개선할 수 있다.
- 하지만, 이 방법으로 개선한다해도 Quick Sort의 최악의 시간 복잡도가 O(nlog₂n)가 되는 것은 아니다.
장점
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환
- 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간복잡도가 O(N logN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
단점
- 불안정 정렬이다.
- 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.