퀵 정렬(Quick Sort)
동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고
https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz
실전 알고리즘 강좌 (Algorithm Programming Tutorial)
www.youtube.com
퀵 정렬(Quick Sort)
특정한 값(피벗)을 기준으로 큰 숫자와 작은 숫자를 나누자
피벗(Pivot) : 퀵 정렬에서의 기준 값, 보통 첫 번째 원소를 피벗값으로 지정
하나의 큰 문제를 두 개의 작은 문제로 분할하는 방식으로 빠르게 정렬 ▶ 분할 정복 알고리즘의 대표적 예
평균 시간 복잡도 : O(N*logN)
최악의 시간 복잡도 : O(N^2)
분할 정복의 이점을 사용하지 못하면 최악의 시간복잡도가 나옴. 피벗값이 배열의 중간쯤 있어야 왼쪽 오른쪽 나누어 각각 퀵 정렬을 수행할 텐데 피벗값이 너무 치우쳐서 왼쪽에 값이 없거나 정렬된 수들만 있을 경우 최악의 시간 복잡도가 나옴
=> 이미 정렬이 되어있거나 거의 정렬이 되어있을 때
ex) 1 2 3 4 5 6 7 8 9 10
원리
3 7 8 1 5 9 6 10 2 4
위와 같이 정렬되지 않은 수들이 주어졌다고 했을 때 먼저 피벗값 = 3
배열의 가장 왼쪽에서 →으로 가면서 피벗값(3) 보다 큰 값을 찾고(7), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(3)보다 작은 값을 찾음(2)
3 7 8 1 5 9 6 10 2 4
큰 값(7)과 작은 값(2) 자리바꾸기
3 2 8 1 5 9 6 10 7 4
다시 배열의 가장 왼쪽에서 →으로 가면서 피벗값(3) 보다 큰 값을 찾고(8), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(3) 보다작은 값을 찾음(1)
3 2 8 1 5 9 6 10 7 4
큰 값(8)과 작은 값(1) 자리 바꾸기
3 2 1 8 5 9 6 10 7 4
다시 배열의 가장 왼쪽에서 →으로 가면서 피벗값(3) 보다 큰 값을 찾고(8), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(3) 보다작은 값을 찾음(1)
3 2 1 8 5 9 6 10 7 4
작은 값의 인덱스 < 큰 값의 인덱스 ▶ 큰 값과 작은 값의 자리가 바뀜(원래라면 큰 값이 좌측에 있어서 서로 자리를 바꿈으로써 작은 값이 좌측에, 큰 값이 우측에 위치해야 함) ▶ 엇갈림
엇갈린 경우 작은 값(1)과 피벗값(3) 자리 바꾸기
1 2 3 8 5 9 6 10 7 4
피벗값(3)이 자리를 옮김으로써 이 값(3)은 정렬됨
∴ 3보다 왼쪽은 3보다 작은 값 / 3보다 오른쪽은 3보다 큰 값 ▶ 1번의 분할이 일어난 것(작은 값 | 큰 값)
정렬된 3을 기준으로 왼쪽 집합 : 1 2 / 오른쪽 집합 : 8 5 9 6 10 7 4에서 각각 피벗값 선택
왼쪽 집합 피벗값 = 1
오른쪽 집합 피벗값 = 8
먼저 왼쪽 집합부터 퀵 정렬 수행
1 2
배열의 가장 왼쪽에서 →으로 가면서 피벗값(1) 보다 큰 값을 찾고(2), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(1) 보다작은 값을 찾음(없음 ▶ 없으면 피벗값 자기 자신 선택 = 1)
1 2
작은 값의 인덱스 < 큰 값의 인덱스 ▶ 큰 값과 작은 값의 자리가 바뀜(원래라면 큰 값이 좌측에 있어서 서로 자리를 바꿈으로써 작은 값이 좌측에, 큰 값이 우측에 위치해야 함) ▶ 엇갈림
엇갈린 경우 작은 값(1)과 피벗값(1) 자리 바꾸기(그냥 그대로) ▶ 1 정렬
1 2 3 8 5 9 6 10 7 4
정렬된 1을 기준으로 1보다 왼쪽은 1보다 작은 값(없음) / 1보다 오른쪽은 1보다 큰 값
왼쪽 집합(1 2)에서 1 정렬했으니까 2 차례
2도 똑같이 수행 ▶ 2 앞 뒤로 정렬된 수가 있으므로 정렬되지 않은 데이터는 2 한 개 (그냥 내버려 둠) ▶ 2 정렬
1 2 3 8 5 9 6 10 7 4
오른쪽 집합 퀵 정렬 수행
8 5 9 6 10 7 4
왼쪽에서 →으로 가면서 피벗값(8) 보다 큰 값을 찾고(9), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(8) 보다작은 값을 찾음(4)
8 5 9 6 10 7 4
큰 값(9)과 작은 값(4) 자리 바꾸기
8 5 4 6 10 7 9
다시 왼쪽에서 →으로 가면서 피벗값(8) 보다 큰 값을 찾고(10), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(8) 보다작은 값을 찾음(7)
8 5 4 6 10 7 9
큰 값(10)과 작은 값(7) 자리 바꾸기
8 5 4 6 7 10 9
다시 왼쪽에서 →으로 가면서 피벗값(8) 보다 큰 값을 찾고(10), 배열의 가장 오른쪽에서 ←으로 가면서 피벗값(8) 보다작은 값을 찾음(7)
8 5 4 6 7 10 9
작은 값의 인덱스 < 큰 값의 인덱스 ▶ 큰 값과 작은 값의 자리가 바뀜(원래라면 큰 값이 좌측에 있어서 서로 자리를 바꿈으로써 작은 값이 좌측에, 큰 값이 우측에 위치해야 함) ▶ 엇갈림
엇갈린 경우 작은 값(7)과 피벗값(8) 자리 바꾸기
7 5 4 6 8 10 9
피벗값(8)이 자리를 옮김으로써 이 값(8)은 정렬됨
∴ 8보다 왼쪽은 8보다 작은 값 / 8보다 오른쪽은 8보다 큰 값 ▶ 1번의 분할이 일어난 것(작은 값 | 큰 값)
이런 식으로 또 8을 기준으로 8보다 작은 왼쪽 집합(7 5 4 6), 8보다 큰 오른쪽 집합(10 9) 각각 퀵 정렬 수행
package algorithmProgramming;
public class QuickSort {
private static void show(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
private static void quickSort(int[] data, int startIdx, int endIdx) {
// 원소가 1개면 그대로 종료
if (startIdx >= endIdx) return;
int pivot = data[startIdx];
int pivotIdx = startIdx;
int leftIdx = startIdx + 1;
int rightIdx = endIdx;
while (leftIdx <= rightIdx) {
// leftIdx가 endIdx를 넘어가지 않고, pivot보다 큰 값을 찾을 때까지 leftIdx++
while (leftIdx <= endIdx && data[leftIdx] <= pivot) {
leftIdx++;
}
// rightIdx가 startIdx보다 작아지지 않고, pivot보다 작은 값을 찾을 때까지 rightIdx--
// but startIdx와 동일해지면 안됨 pivot의 인덱스가 startIdx이므로
while (rightIdx > startIdx && data[rightIdx] >= pivot) {
rightIdx--;
}
// 위 while문을 통해 각각 작은값과 큰값을 찾음
if (leftIdx < rightIdx) { // leftIdx와 rightIdx가 만나지 않으면 서로 자리 바꿈
int tmp = data[leftIdx];
data[leftIdx] = data[rightIdx];
data[rightIdx] = tmp;
} else { // leftIdx와 rightIdx가 만났다면 pivot값과 rightIdx의 값 자리 바꿈
int tmp = data[rightIdx];
data[rightIdx] = data[pivotIdx];
data[pivotIdx] = tmp;
}
}
quickSort(data, startIdx, rightIdx - 1);
quickSort(data, rightIdx + 1, endIdx);
}
public static void main(String[] args) {
int[] data = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
System.out.print("정렬 전 : ");
show(data);
System.out.println();
quickSort(data, 0, data.length - 1);
System.out.print("정렬 후 : ");
show(data);
}
}
