퀵 정렬(Quick Sort)
1. 리스트에서 하나의 요소를 피벗(Pivot)으로 선택한다.
2. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분류한다.
- 이를 분할(Partition)이라 한다.
3. 분할된 두 부분 리스트를 각각 재귀적으로 퀵 정렬한다.
4. 리스트가 하나의 요소만 남을 때까지 재귀 호출을 반복한다.
장점
평균 시간 복잡도: O(nlogn)
공간 효율성이 뛰어남(in-place 정렬 가능)
정렬해야 할 데이터가 많을수록 효과적
단점
최악의 경우 시간 복잡도: O(n^2) (피벗 선택이 좋지 않을 때)
public class QuickSort {
public static void quickSort(int[] arr, int low, int high){
System.out.println("quickSort low: " + low + ", high: " + high);
// low가 high와 같거나 크면 종료한다.
if(low < high){
// 피벗을 기준으로 배열을 두 부분으로 나누고, 피벗 인덱스를 반환한다.
int pi = partition(arr, low, high); // 분할 지점 계산
System.out.println("pi: " + pi);
// 최초는 arr, 0, 0이 들어간다.
quickSort(arr, low, pi - 1); // 피벗을 중심으로 한 왼쪽 배열 정렬
// 최초는 arr, 2, 5가 들어간다
// low가 바뀐다. pi + 1이 된다.
quickSort(arr, pi + 1, high); // 피벗을 중심으로 한 오른쪽 배열 정렬
}
}
// 피벗: 퀵 정렬에서 배열을 분할하기 위해 선택된 기준 값
// 피벗을 기준으로 배열의 요소를 두 부분으로 나눈다.
// 1. 피벗보다 작은 값들은 배열의 왼쪽 부분으로 이동한다.
// 2. 피벗보다 큰 값들은 배열의 오른쪽 부분으로 이동한다.
// 이 과정을 분할이라 하며, 이를 반복하여 배열을 정렬한다.
// 퀵 정렬의 핵심은 분할 정복(Divide and Conquer) 전략이다.
// 퀵 정렬의 전체 과정
// 피벗을 기준으로 배열을 두 부분으로 나눈다.
// 피벗보다 작은 값: 왼쪽 배열
// 피벗보다 큰 값: 오른쪽 배열
// 이 과정이 끝나면 피벗은 자신의 올바른 위치(정렬된 위치)에 있게 된다.
// 왼쪽 배열과 오른쪽 배열을 각각 재귀적으로 정렬한다.
// 각각의 부분 배열에서 새로운 피벗을 선택하고, 다시 분할 과정을 수행한다.
// 재귀적으로 계속 나누다 부분 배열의 크기가 1 이하가 되면 더 이상 정렬이 필요없기에 종료한다.
// 퀵 정렬에서 최악의 경우와 최선의 경우는 피벗 선택에 따라 발생한다.
// 1. 최악의 경우(Worst Case)
// 피벗이 항상 배열에서 가장 크거나 가장 작은 값으로 선택될 때 발생한다.
// 분할이 한쪽으로 치우치고, 배열을 균등하게 나눌 수 없다.
// 배열이 이미 정렬돼 있거나 역순으로 정렬된 상태일 때 최악의 경우가 발생한다.
// 이 과정을 배열 크기만큼 반복하여 재귀 호출 깊이 O(n)이 된다.
// 최종적으로 시간복잡도는 O(n^2)이다.
// 2. 최선의 경우(Best Case)
// 피벗이 항상 배열을 정확히 반으로 나누는 값으로 선택될 때 발생한다.
// 배열을 최대한 균등하게 나눌 수 있어 분할 정복의 효율이 극대화된다.
// 각 단계에서 배열을 반으로 나누면 O(logn) 단계가 필요하고,
// 각 단계에서 배열의 모든 요소를 비교하므로 O(n)의 작업량이 발생한다.
// 최선의 경우 시간 복잡도는 O(nlogn)이다.
// 3. 평균적인 경우(Average Case)
// 피벗이 배열을 대략적으로 균등하게 나누는 값으로 선택될 때 발생한다.
// 대부분의 경우 랜덤한 배열에서 발생하며, 최선의 경우와 비슷한 성능을 보인다.
// 시간 복잡도는 평균적으로 O(nlogn)이 된다.
private static int partition(int[] arr, int low, int high){
System.out.println("parition low: " + low + ", high: " + high);
int pivot = arr[high]; // 피벗 선택, 일반적으로 배열 마지막 값을 피벗으로 선택한다.
// 첫 번째 피벗은 5이다.
// 5보다 작은 값은 1 뿐이다.
System.out.println("pivot: " + pivot);
System.out.println();
// i는 -1로 들어간다.
int i = (low - 1); // 작은 요소의 인덱스
// System.out.println("i: " + i);
for(int j = low; j < high; j++){
if(arr[j] < pivot){
// j == 4에서 걸린다
// j == 4는 1이다.
System.out.println("j: " + j);
System.out.println("i1: " + i);
System.out.println("arr[j]: " + arr[j]);
i++;
// 요소 교환
// i는 -1에서 시작한다. 1을 더하면 0이 된다.
// arr[i]는 0번째 요소이고 10이 된다.
// 피벗보다 작은 값을 0번째 요소와 교체한다. 서로 자리를 바꾼다. 정렬이 한 번 일어난 것이다.
int temp = arr[i];
System.out.println("temp: " + temp);
arr[i] = arr[j];
arr[j] = temp;
}
}
System.out.println("i2: " + i);
// 피벗을 올바른 위치로 이동
// i는 피벗보다 작은 값의 마지막 인덱스이다.
// i + 1은 피벗이 들어갈 위치이다.
// i +1과 피벗(high)를 교체한다.
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 피벗 인덱스를 반환한다.
return i + 1; // 분할 지점 반환
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
quickSort(arr, 0, n - 1);
System.out.println("정렬된 배열" );
for(int num : arr){
System.out.println(num + " ");
}
}
}
피벗 선택에 따라 성능이 크게 달라진다.
- 랜덤한 피벗 선택: 최적화된 성능
- 첫 번째 또는 마지막 요소를 피벗으로 선택: 최악의 성능 발생 가능
대규모 데이터 정렬에 적합하다.
마지막 요소를 피벗으로 쓰는 건 구현이 간단하지만 이미 정렬된 데이터의 경우엔 피벗이 항상 가장 크거나 작은 값으로 선택되며 O(n^2)의 성능이 나온다.
연습 목적이나 랜덤 데이터에 대한 정렬에선 마지막 요소를 피벗으로 선택해도 좋지만, 실제론 최악의 경우를 방지하기 위해 Median-of-Three 또는 랜덤 피벗 전략을 더 많이 사용한다.
데이터의 패턴이 명확하지 않을 땐 랜덤 피벗이 가장 안전한 선택이다.
데이터가 이미 정렬된 상태일 수 있다면 Median-of-Three 방식이 효과적이다.
Median-of-Three는 세 값의 중앙값을 선택하는 것으로 배열의 첫 번째, 중간, 마지막 요소 중 중앙값을 피벗으로 선택하는 것이다. 중앙값을 선택하면 분할의 균형을 맞추는데 효과적이다.
랜덤 피벗(Random Pivot)은 배열 내에서 임의의 인덱스를 피벗으로 선택하는 것이다. 특정 데이터 패턴에서 발생할 수 있는 최악의 경우를 방지하는데 효과적이다.
메서드에 static을 쓰지 않아도 배열 참조 전달과 원본 배열 변경은 동일하게 동작한다.
static 키워드는 메서드나 변수의 속성(정적 또는 비정적)을 결정하는 요소일 뿐이고, 배열 참조 전달, 원본 배열 변경과는 무관하다.