일반적으로 많이 사용되는 알고리즘으로 불안정 정렬 (같은 값인 경우, 순서 보장 안됨) 이다.
그룹 중 하나를 선택하고 (피벗, Pivot), 피벗을 기준으로 왼쪽, 오른쪽으로 그룹을 나누고 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰값을 정렬한다.
이를 피벗을 기준으로 서브 리스트로 나뉘어서 위 과정을 길이가 1일 될때 까지 반복하고, 다시 합치는 것이다.
시간복잡도는 최선은 O(nlogn), 최악은 O(n²) 이다.
정렬 방법
피벗이 앞쪽이냐 뒤쪽이냐에 따라 구현 방법이 달라지는데 중간에 있다고 가정하겠다.
1. 피벗을 하나 선택한다.
2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
3. 양 방향에서 찾은 두 원소를 교환한다.
4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 때 까지 2번으로 돌아가 위 과정을 반복한다.
5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번 과정을 반복한다. (Divide : 분할)
6. 인접한 부분리스트끼리 합친다. (Conqure : 정복)자바로 작성하면 다음과 같다.
static void quick_sort(int[] arr, int left, int right) {
int low = left;
int high = right;
int mid = (left + right) / 2;
int pivot = arr[mid];
while (low <= high) {
while (arr[low] < pivot) {
low++;
}
while (pivot < arr[high]) {
high--;
}
if (low <= high) {
swap(arr, low, high);
low++;
high--;
}
}
if (low < right) {
quick_sort(arr, low, right);
}
if (left < high) {
quick_sort(arr, left, high);
}
}
static void swap(int[] arr, int i , int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}참조한 책 및 사이트
https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC