[Java] Quick Sort(퀵 정렬, 재귀 방식, 왼쪽/중간/오른쪽 피벗)
설명
- 피벗을 기준으로 좌측에 피벗 보다 작은 값, 우측에 피벗보다 큰 값을 위치 시킴
- partition(파티션)을 나눠 행위를 반복한다
- partition을 최소 까지 나눴을 때는 이미 정렬이 완료된 상태이다.
파티션을 나누기 전에 pivot 기준으로 임의 정렬을 하고 partition을 나눠 행위 반복하면 더이상 나눌 수 없을 때 이미 정렬이 완료된다. <-> 반대로 merge sort의 경우 제일 작은 크기 까지 파티션을 먼저 나눈 후 병합을 하면서 정렬 수행한다.
*과정
(1) pivot 을 정함
(2) 양쪽 끝에 L, R 포인터를 두고 다음 수행
2-1) L < pivot 경우 포인터 증가 L += 1 (pivot 기준 좌변은 항상 작아야 하므로, 큰 값이 나올 때까지 포인터 이동)
2-2) pivot > R 경우 포인터 감소 R -= 1 (pivot 기준 우변은 항상 커야 하므로, 작은 값이 나올 때 까지 포인터 이동)
2-3) 탐색 범위 내 일 경우 swap(arr, L, R) 후 재탐색
(3) 포인터가 교차 할 경우, 최종 피벗 위치 기준으로 왼쪽/오른쪽 파티션을 나눠서 1)번부터 반복한다
Tip. 개인 기록
- 왼쪽 피벗의 경우 R 포인터를 먼저 움직이고 R을 기준으로 파티션을 나눈다
- 오른쪽 피벗의 경우 L 포인터를 먼저 움직이고 L을 기준으로 파티션을 나눈다
- 중앙 피벗의 경우 어느 포인터든 상관없이 교차할 때 (왼쪽, R) , (L, 오른쪽) 파티션을 나눈다
(swap시 L , R 포인터 각각 한칸 씩 이동)
영상 참고
https://www.youtube.com/watch?v=h8eyY7dIiN4
참고. 중앙 피벗 (이미지)
- 파티션 분할 (왼쪽, R) , (L, 오른쪽)
- (왼쪽, R) 파티션 : quick 정렬 수행
- 파티션 분할 (왼쪽, R) , (L, 오른쪽)
- (L, 오른쪽) 파티션 : quick 정렬 수행
참고. 왼쪽 피벗 (이미지)
참고. 오른쪽 피벗 (이미지)
코드
1) middle pivot (중앙 피벗)
- L 과 R 이 교차하기 전까지 탐색과 swap 수행
- L > R이 교차했을 때, (시작 인덱스 ~ R), (L ~ 마지막 인덱스) 파티션 분할
private static void quickSort(int[] arr) {
quickSortByMidPivot(arr, 0, arr.length - 1);
}
private static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
private static void quickSortByMidPivot(int[] arr, int leftIdx, int rightIdx) {
if(leftIdx >= rightIdx) return;
int mid = (leftIdx + rightIdx) / 2;
int pivot = arr[mid];
int L = leftIdx;
int R = rightIdx;
while(L <= R) {
while(arr[L] < pivot) L += 1;
while(pivot < arr[R]) R -= 1;
if(L <= R) {
swap(arr, L, R);
L += 1;
R -= 1;
}
}
quickSortByRightPivot(arr, leftIdx, R);
quickSortByRightPivot(arr, L, rightIdx);
}
public static void main(String[] args) {
int[] data = new Random().ints(1, 99).distinct().limit(7).toArray();
System.out.println(Arrays.toString(data));
quickSort(data);
System.out.println(Arrays.toString(data));
}
2) left pivot(왼쪽 피벗)
- L과 R이 겹치기 전까지 탐색과 swap 수행
- 포인터 R 부터 먼저 움직이고, 파티션을 나눌 때도 R을 기준으로 나눈다
private static void quickSort(int[] arr) {
quickSortByLeftPivot(arr, 0, arr.length - 1);
}
private static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
private static void quickSortByLeftPivot(int[] arr, int leftIdx, int rightIdx) {
if(leftIdx >= rightIdx) return;
int pivot = arr[leftIdx];
int L = leftIdx;
int R = rightIdx;
while(L < R) {
while(pivot < arr[R] && L < R) R -= 1;
while(arr[L] < pivot && L < R) L += 1;
if(L >= R) break;
swap(arr, L, R);
}
quickSortByLeftPivot(arr, leftIdx, R - 1);
quickSortByLeftPivot(arr, R + 1, rightIdx);
}
public static void main(String[] args) {
int[] data = new Random().ints(1, 99).distinct().limit(7).toArray();
System.out.println(Arrays.toString(data));
quickSort(data);
System.out.println(Arrays.toString(data));
}
3) right pivot (오른쪽 피벗)
- L과 R이 겹치기 전까지 탐색과 swap 수행
- 포인터 L 부터 먼저 움직이고, 파티션을 나눌 때도 L을 기준으로 나눈다
private static void quickSort(int[] arr) {
quickSortByLeftPivot(arr, 0, arr.length - 1);
}
private static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
private static void quickSortByRightPivot(int[] arr, int leftIdx, int rightIdx) {
if(leftIdx >= rightIdx) return;
int pivot = arr[rightIdx];
int L = leftIdx;
int R = rightIdx;
while(L < R) {
while(arr[L] < pivot && L < R) L += 1;
while(pivot < arr[R] && L < R) R -= 1;
if(L >= R) break;
swap(arr, L, R);
}
quickSortByRightPivot(arr, leftIdx, L - 1);
quickSortByRightPivot(arr, L + 1, rightIdx);
}
public static void main(String[] args) {
int[] data = new Random().ints(1, 99).distinct().limit(7).toArray();
System.out.println(Arrays.toString(data));
quickSort(data);
System.out.println(Arrays.toString(data));
}
중앙 피벗
정렬 전 [3, 27, 16, 97, 57, 35, 20]
정렬 후 [3, 16, 20, 27, 35, 57, 97]
왼쪽 피벗
정렬 전 [47, 76, 25, 91, 29, 95, 71]
정렬 후 [25, 29, 47, 71, 76, 91, 95]
오른쪽 피벗
정렬 전 [16, 92, 50, 18, 98, 73, 51]
정렬 후 [16, 18, 50, 51, 73, 92, 98]