🚀 퀵 정렬 알고리즘 실제 코드로 구현하기

지난 시간에 예시로 든 배열 [7, 3, 5, 2, 8, 1, 4, 6]을 오름차순으로 정렬하겠습니다

public static void main(String[] args) throws IOException {  

    int[] arr = {7,3,5,2,8,1,4,6};  
    quickSort(arr, 0, arr.length-1);  

    for (int i : arr) {  
        bw.write(i+" ");  
    }  
  
}

private static void quickSort(int[] arr, int left, int right) {  
    if(left < right){  
        int pivot = partition(arr, left, right);  
        quickSort(arr, left, pivot-1);  
        quickSort(arr, pivot+1, right);  
    }  
}  
  
private static int partition(int[] arr, int left, int right) {  
    int pivot = arr[right];  
    int l = left - 1;  
    for (int i = left; i < right; i++) {  
        if(arr[i] <= pivot){  
            l++;  
            swap(arr, l, i);  
        }  
    }  
    swap(arr, l+1, right);  
    return l+1;  
}  
  
private static void swap(int[] arr, int l, int r){  
    int tmp = arr[l];  
    arr[l] = arr[r];  
    arr[r] = tmp;  
}

이 코드를 실행하면 배열을 [1, 2, 3, 4, 5, 6, 7, 8]의 형태로 오름차순 정렬합니다

🔍 피벗 선택이 편향되는 경우

피벗 선택이 편향되는 경우, O(n²)의 최악 시간복잡도가 됩니다

피벗 선택이 편향되는 경우는 다음과 같습니다:

📌 이미 정렬된 배열에서 항상 첫 번째 원소나 마지막 원소를 피벗으로 선택하는 경우:

[1, 2, 3, 4, 5] 에서 마지막 원소를 피벗으로 선택하면,
정렬할 구간이 거의 줄지 않아 한쪽에만 계속 재귀가 발생합니다

📌 역순으로 정렬된 배열에서도 동일한 방식의 피벗 선택하는 경우:

[5, 4, 3, 2, 1] 에서 첫 번째 원소를 피벗으로 고정하면, 분할이 계속 한쪽으로만 일어납니다

📌 중복된 값이 많은 배열에서 적절하지 않은 피벗 선택을 할 경우:

[5, 5, 5, 5, 5]와 같이 동일한 값만 있는 배열은 의미 있는 분할이 이뤄지지 않습니다

이처럼 균형 잡히지 않은 분할이 계속되면, 재귀 깊이가 커지고 성능이 저하됩니다

🛠️피벗선택 편향 문제 해결방법

📌무작위 피벗 선택

배열에서 피벗을 처음이나 마지막에서 고르지 않고, left ~ right 범위 내에서 무작위로 선택하는 방식입니다

-> 항상 같은 위치에서 피벗을 선택하면 정렬된 배열에서 성능이 나빠지므로,
무작위로 선택함으로써 편향을 방지하고 평균적인 분할을 기대할 수 있습니다

📌중앙값 기법

배열의 중앙값(median)**을 피벗으로 선택하는 방식입니다

-> 중앙값을 선택함으로써 균형 잡힌 분할이 가능하고, 최악의 시간복잡도 (O(n²)) 발생 가능성도 줄어듭니다

📌하이브리드 정렬 방식 적용

퀵 정렬을 사용하되, 재귀적으로 쪼개는 과정에서 서브배열 크기가 작아지면 다른 정렬 알고리즘로 전환합니다

-> 작은 배열에서는 퀵 정렬의 오버헤드가 오히려 손해일 수 있으므로,
단순하지만 효율적인 삽입 정렬로 대체해 성능을 향상시킵니다

✍️결론

퀵 정렬은 평균적으로 매우 빠른 정렬 알고리즘이지만,
피벗 선택이 편향되면 최악의 경우 시간복잡도가 O(n²)까지 저하될 수 있습니다

이러한 문제를 방지하기 위해서는
무작위 피벗 선택, 중앙값 기법, 하이브리드 정렬 전략을 통해 퀵 정렬의 단점을 보완할 수 있습니다