- 퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다.
- 분할 정복(Divide and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
- 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
- 또한, Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.
- 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소는 피벗(pivot)이라고 한다.
- 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
- 분할 된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
- 분할(Divide) : 주어진 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다.(피벗을 중으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)
- 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
private static void quickSort(int[] arr, int left, int right) {
int L = left;
int R = right;
int pivot = arr[(left + right) / 2];
// 피벗을 배열의 가운데 위치한 요소로 설정.
while (L <= R) {
// 피벗 왼쪽에는 피벗보다 작은 원소들이 위치해야 하고, 큰 원소가 있다면 반복문을 나온다.
while (arr[L] < pivot) L++;
// 피벗 오른쪽에는 피벗보다 큰 원소들이 위치해야 하고, 작은 원소가 있다면 반복문을 나온다.
while (pivot < arr[R]) R--;
// L과 R이 역전되지 않고, 같은 경우가 아니라면 두 원소의 위치를 교환한다.
// 이를 통해서 피벗 기준으로 왼쪽에는 작은 원소가, 오른쪽에는 큰 원소가 위치하게 된다.
if (L <= R) {
if (L != R) {
swap(arr, L, R);
}
L++;
R--;
}
}
// L과 R이 역전된 후에 피벗의 왼쪽과 오른쪽에는 정렬되지 않은 부분 배열이 남아있을 수 있다.
// 이 경우, 남아 있는 부분 배열에 대해서 퀵 정렬을 수행한다.
if (left < R) quickSort(arr, left, R);
if (L < right) quickSort(arr, L, right);
}
// 입력 받은 원소의 자리를 교환해준다.
private static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}위의 코드에서는 피벗을 배열의 가운데 원소로 지정함으로써 어느 정도 성능을 개선한 형태이다.
하지만, 피벗 값이 최소나 최대값으로 지정되면 피벗을 기준으로 원소들이 들어갈 값을 찾는데 오래 걸린다. O(N^2)의 시간 복잡도를 갖는다.
즉, 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있으면 O(N^2)의 시간복잡도를 가진다. 이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간 복잡도 O(N logN)으로 개선할 수 있다.
하지만, 이 방법으로 개선한다 하더라도 Quick Sort의 최악의 시간 복잡도가 O(N logN)이 되는 것은 아니다.
최선의 경우 : T(N) = O(N logN)
- 비교 횟수 : logN
레코드의 개수 N이 2의 거듭제곱이라고 가정했을 때(N = 2^k), N = 2^3의 경우
2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.
이것을 일반화하면 N = 2^k의 경우, k = logN임을 알 수 있다.
[각 순환 호출 단계의 비교 연산] (N)
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 N번 정도의 비교가 이루어진다.
따라서, 최선의 시간 복잡도는 순환 호출의 깊이(logn) x 각 순환 호출 단계의 비교 연산(n) = n logn이 된다.
이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.
최악의 경우 : T(N) = O(N^2)
최악의 경우는 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있는 경우이다.
- 비교 횟수 : (N)
레코드의 개수 N이 2의 거듭제곱이라고 가정했을 때(N = 2^k), 순환 호출의 깊이는 N임을 알 수 있다.
- 각 순환 호출 단계의 비교 연산
각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 N번 정도의 비교가 이루어진다.
따라서 최악의 시간 복잡도는 순환 호출의 깊이 x 각 순환 호출 단계의 비교 연산 = N^2 이다.
이동횟수는 비교 횟수보다 적으므로 무시할 수 있다.
주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(N logN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
- 불안정 정렬이다.
- 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.
Quick Sort는 평균적으로 가장 빠른 정렬 알고리즘이다.
Java에서는 Arrays.sort()가 내부적으로 Dual Pivot Quick Sort로 구현되어 있을 정도로 효율적인 알고리즘이다.
또한, 기술 면접에서 빈번하게 나오므로 반드시 숙지해야 한다.