[정렬] 퀵 정렬

퀵정렬

분할 정복(Divide and Conquer) 방식으로 배열을 반씩 나누어 정렬한 후 병합(Merge)하는 방식이다.

복잡도

평균 $O(nlogn)$ : 분할이 균형있게 일어나는 경우

최악 $O(n^2)$ : 피봇이 항상 한 쪽 끝(예: 이미 정렬된 배열)을 선택할 경우

로직

1. 피봇 선택
   • 배열의 가운데 값low+high)/2 을 피봇으로 정한다.
2. 분할(Partitioning)
   • 왼쪽 인덱스 low 는 피봇보다 큰 값을 만날 때 까지 이동
   • 오른쪽 인덱스 high 는 피봇보다 작은 값을 만날 때까지 이동
   • 두 값을 교환 : swap
   • low 가 high 보다 커질 때까지 반복
3. 재귀 호출
   • 피봇 기준 왼쪽 구간과 오른쪽 구간을 각각 퀵 정렬로 수행
   • 구간의 크기가 1 이하가 되면 재귀 종료

코드 예시

import java.util.Arrays;

public class QuickSortExample {
    public static void solution(int[] arr) {
        /* 예시: [5, 3, 8, 9, 2, 4, 7] */
        System.out.println("원본 배열 : " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("정렬된 배열 : " + Arrays.toString(arr));
    }

    private static void quickSort(int[] arr, int low, int high) {
        if (low >= high) return; // 종료 조건: 구간 크기가 1 이하일 때
        int partitionIndex = partition(arr, low, high);
        // partitionIndex는 오른쪽 구간의 시작점
        quickSort(arr, low, partitionIndex - 1);  // 왼쪽 구간
        quickSort(arr, partitionIndex, high);     // 오른쪽 구간
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2]; // 가운데 값 선택
        System.out.println("Pivot : " + pivot + " | 범위: " + low + " ~ " + high);
        System.out.println("분할 전 : " + Arrays.toString(arr));

        while (low <= high) {
            while (arr[low] < pivot) low++;
            while (arr[high] > pivot) high--;
            if (low <= high) { // 엇갈리지 않았다면 교환
                swap(arr, low, high);
                low++;
                high--;
            }
        }

        System.out.println("분할 후 : " + Arrays.toString(arr));
        System.out.println("반환할 분할 기준 인덱스 : " + low);
        System.out.println("===============================");
        return low; // 오른쪽 파티션의 시작 인덱스
    }

    private static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 9, 2, 4, 7};
        solution(arr);
    }
}

퀵 정렬 시각화

초록색이 high, 파란색이 low , 빨간색이 partitionIndex이다.