1. 정의 👨🚀
빠른 정렬실버 분할 정복 방법를 이용하는 정렬 알고리즘입니다.
빠른 정렬은 피벗에 따라 분할그리고 정복이렇게 된다.
퀵 정렬은 “피벗 선택 방법”과 “재귀 또는 비 재귀 방식”의 선택에 따라 다양한 구현 방법이 있습니다.
이 기사에서는 왼쪽 피벗을 선택하는 방법그리고 「재귀 방식」에서 빠른 정렬을 살펴 보겠습니다.
2. 동작 방식 🦸♂️
기본 동작 방법는 다음과 같습니다.
- 배열에서 원하는 요소인 피벗을 선택합니다.
(이 기사에서는 배열의 가장 왼쪽 요소를 pivot로 선택합니다.
) - 피벗에 기초하여, 피벗보다 작은 원소는 좌측으로, 피벗보다 큰 원소는 우측으로 오도록 배열을 배치한다.
- pivot을 기준으로 분할된 왼쪽 배열과 오른쪽 배열에 1~2회의 절차를 반복한다.
(재귀 방식 사용)
pivot을 기반으로 “피벗보다 작은 원소를 왼쪽으로, pivot보다 큰 원소를 오른쪽으로”배치하는 방법에 대해 자세히 알아보십시오. 왼쪽부터 시작하는 포인터(lo)그리고 오른쪽에서 시작하는 포인터(hi)를 사용하여 pivot을 기준으로 원소를 나눌 것입니다.
인기글
- hi와 lo라는 인덱스를 가리키는 포인터를 설정합니다.
(잘 알고 있는 실제 포인터가 아닙니다.
) - hi는 pivot보다 작은 값을 만날 때까지 왼쪽으로 이동합니다.
- lo는 pivot보다 큰 값을 만날 때까지 오른쪽으로 이동합니다.
- 두 포인터가 가리키는 값을 변경합니다.
- lo가 hi 이하일 때까지 2~5회 반복한다.
- pivot과 lo를 바꿉니다.
{5, 3, 7, 8, 2, 4, 6}의 배열이 피벗을 기준으로 어떻게 정렬되는지 그림에서 살펴보겠습니다.
마지막으로 pivot인 5와 lo인 2를 바꾸어 주면 pivot인 5는 자신의 자리에 방문한 것이다.
따라서, 피벗을 기준으로 좌측에는 피벗보다 작은 원소가, 우측에는 피봇보다 큰 원소가 위치하게 된다.
계속해서 피벗을 바탕으로 왼쪽 영역그리고 오른쪽 영역을 나란히 합시다.
정렬이 이루어지는 과정에서 3개주목하면 쉽게 이해할 수 있다.
- hi와 lo가 pivot보다 작은 것을 찾을 때까지 pivot보다 큰 값이 발견될 때까지 이동합니다.
- lo는 hi보다 큰 색인을 가리키지 않습니다.
- 더 이상 움직이지 않으면 pivot과 lo를 교체하십시오.
이와 같이 분할된 배열을 합치면, 정렬된 배열이 된다.
3. 구현(JAVA) 🧙♂️
public static void main(String() args) {
int() array = {5, 3, 7, 8, 2, 4, 6};
quickSort(array, 0, array.length - 1);
}
static void quickSort(int() array, int left, int right) {
if(left >= right)
return;
// pivot을 기준으로
// 왼쪽에는 pivot보다 작은 것들이
// 오른쪽에는 pivot보다 큰 것들이
// 위치하도록 하는 것
int pivot = partition(array, left, right);
// 왼쪽 영역에 대해서 다시 정렬
quickSort(array, left, pivot - 1);
// 오른쪽 영역에 대해서 다시 정렬
quickSort(array, pivot + 1, right);
}
static int partition(int() array, int left, int right) {
int pivot = array(left);
int lo = left, hi = right;
while(lo < hi) {
// hi가 pivot보다 작은 것을 찾을 때까지 왼쪽으로 이동
while(pivot < array(hi)) {
hi--;
}
// lo가 pivot보다 큰 것을 찾을 때까지 오른쪽으로 이동
// lo는 hi보다 큰 인덱스 값을 가질 수 없다!
!
while(lo < hi && pivot >= array(lo)) {
lo++;
}
// lo가 가르키는 것과 hi가 가르키는 것을 교체
swap(array, lo, hi);
}
// pivot과 lo를 교체
// 교체하게 되면 pivot을 기준으로 왼쪽에는 작은 값
// 오른쪽에는 큰 값들이 위치함.
array(left) = array(lo);
array(lo) = pivot;
// pivot의 위치를 return
return lo;
}
private static void swap(int() array, int i, int j) {
int temp = array(i);
array(i) = array(j);
array(j) = temp;
}
4. 시간의 복잡성과 공간의 복잡성 🦹♂️
1. 시간의 복잡성
빠른 정렬의 시간 복잡성은 피벗을 선택하는 방법에 따라 다릅니다.
일반적으로, N개의 노드에 대한 바이너리 트리의 높이는 logN이 되고, 각 레벨에서 N회의 비교와 정렬이 일어난다.
(병합 정렬 참조) 따라서 일반적인 상황에서 시간의 복잡성은 O(N logN)된다.
그러나 최악의 경우는 이야기가 바뀐다.
pivot이 연속적으로 최소값 또는 큰 값이 되면(이미 오름차순 또는 내림차순으로 정렬된 경우) 트리 높이 logN이 아닙니다.
N이것이 된다.
따라서 최악의 경우 시간의 복잡성은 O(N^2)된다.
| 베스트(BEST) | 평균(AVERAGE) | 최악 (WORST) | |
| 시간의 복잡성 | O(N logN) | O(N logN) | O(N^2) |
2. 공간 복잡성
공간 복잡도의 경우 주어진 배열 내에서 교환 (swap)이 발생하기 때문에 O(N)이다.
5. 이점 & 결점 👨🔬
1. 이점
- 시간 복잡도가 O(N logN)인 다른 정렬 알고리즘과 비교하여 상대적으로 빠른. (한 번 결정된 피벗이 다음 연산에서 제외되는 특성에 따라)
- 추가 메모리 공간이 필요하지 않습니다.
2. 단점
- 특정 조건에서 성능이 급격히 떨어집니다.
pivot을 최소값을 선택하거나 큰 값을 계속 선택하여 불균형 분할을 수행하는 경우 - 재귀를 사용하기 때문에 일정 횟수 이상이면 사용할 수 없습니다.
(재귀없이 구현하는 방법이 있지만 복잡합니다.
)
그 기사는
Gyoogle의 빠른 정렬(Quick Sort),
Stranger의 Java-Quick 정렬
를 참고로 했습니다.