분할 정복 기법을 통해 정렬하는 알고리즘이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬이다. 또한, 합병 정렬과 달리 배열을 비균등하게 분할한다.
분할 정복 (Divide and Conquer)
- 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
- 재귀 호출을 이용하여 구현
컴퓨터로 가장 많이 구현된 알고리즘 중 하나이며, 거의 모든 언어에서 제공되는 정렬 함수는 퀵 정렬 혹은 퀵 정렬의 변형 알고리즘을 사용한다.
Java의 Arrays.sort()는 퀵 정렬의 변형 알고리즘인 듀얼피봇 퀵 정렬(Dual-Pivot Quick sort)을 사용한다.
정렬 과정
- 피벗(pivot): 배열에서 원소를 하나 선택한다.
- 난수(Random Quick Sort), 중위법
- 가장 쉽고 비효율적인 방법 - 배열 중에 3개나 9개의 원소를 골라서 이들의 중앙값 선택
- C++과 gcc에서 구현하고 있는 방법
- 최악의 경우가 나올 수 있지만 그 경우가 극히 드물다. - 인트로 정렬
- 퀵 정렬, 삽입 정렬, 힙 정렬로 이루어져 있다.
- 재귀 호출의 깊이가 2^logn을 넘어가게 되면 힙 정렬 알고리즘을 사용하여 항상 O(nlogn)을 보장한다.
- 난수(Random Quick Sort), 중위법
- 분할(Divide): 피벗을 기준으로 왼쪽에는 피벗보다 값이 작은 원소들이 오고, 오른쪽에는 피벗보다 값이 큰 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.
- 정복(Conquer): 부분 배열을 정렬한다. 부분 배열들이 더 이상 분할이 불가능할 때까지 재귀(recursion)적으로 이 과정을 반복한다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
- 재귀 호출이 한 번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
소스 코드
public class Main {
static int[] nums = {1000, 400, 12, -59, 328, 121, -3};
public static void main(String[] args) {
int size = nums.length-1;
quickSort(0, size);
System.out.println(Arrays.toString(nums));
}
// method 1
static void quickSort(int left, int right) {
if(left >= right) {
return;
}
int pivot = partition(left, right);
quickSort(left, pivot-1);
quickSort(pivot+1, right);
}
// method 2
static int partition(int left, int right) {
int pivot = nums[left];
int i = left, j = right;
while(i < j) {
while(pivot < nums[j]) {
j--;
}
while(i < j && pivot >= nums[i]) {
i++;
}
swap(i, j);
}
nums[left] = nums[i];
nums[i] = pivot;
return i;
}
static void swap(int x, int y) {
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}
}method 1: 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할 정복 방법을 이용한다.
method 2: 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 나눈다. 피벗의 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값이 온다.
시간 복잡도
최선의 경우 - O(nlog₂n)
- 비교 횟수
(log₂n)
레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, n=2^3의 경우 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 재귀 호출의 깊이가 3임을 알 수 있다.
따라서 n=2^k의 경우, k(k=log₂n) 임을 알 수 있다. - 비교 연산
(n)
각 재귀 호출에서는 전체 배열의 대부분의 원소를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
따라서, 최선의 시간 복잡도는 재귀 호출의 깊이 * 비교 연산 = nlog₂n 이 된다. 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.
평균의 경우 - O(nlog₂n)
최악의 경우 - O(n^2)
최악의 경우는 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있어 배열이 계속 불균형하게 나누어지는 경우 혹은 피벗을 최솟값이나 최댓값으로 선택하는 경우이다.
- 비교 횟수
(n)
레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, 재귀 호출의 깊이는 n 임을 알 수 있다. - 비교 연산
(n)
각 재귀 호출에서는 전체 배열의 대부분의 원소를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.
따라서, 최악의 시간 복잡도는 재귀 호출의 깊이 * 비교 연산 = n^2 이다. 마찬가지로 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.
공간 복잡도
주어진 배열 안에서 교환(Swap)을 통해 정렬이 수행되므로 O(n) 이다.
장점
- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들은 다음 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n) 인 다른 정렬 알고리즘과 비교했을 때 가장 빠르다.
- 제자리 정렬(in-place sorting) 이므로 다른 메모리 공간을 필요로 하지 않는다.
단점
- 불안정 정렬(unstable sort) 이다.
- 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
- 중간 값(medium)을 피벗으로 선택한다면 확률적으로나마 시간 복잡도를 개선할 수 있지만, 최악의 시간 복잡도가 개선 되는 것은 아니다.
[참고] - gyoogle - 퀵 정렬(Quick Sort)
- Heee's Development Blog - [알고리즘] 퀵 정렬(quick sort)이란
