[java] 퀵 정렬(Quick Sort)

퀵 정렬은 피벗을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다.

피벗이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균적인 시간 복잡도는 O(nlogn)이다.

 

퀵 정렬 핵심 이론

피벗을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심이다.

피벗보다 작으면 왼쪽, 크면 오른쪽으로 정렬하면 된다.

Do it! 알고리즘 코딩 테스트

① 데이터를 분할하는 pivot을 설정한다(위 그림의 경우 가장 오른쪽 끝을 pivot으로 설정).

② pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

• ②-a: start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.
• ②-b: end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.
• ②-c: start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.
• ②-d: start와 end가 만날 때까지 ②-a~②-c를 반복한다.
• ②-e: start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.

③ 분리 집합에서 각각 다시 pivot을 선정한다.

④ 분리 집합이 1개 이하가 될 때까지 과정 ①~③을 반복한다.

 

코드

swap()

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

 

v1()

public static void v1(int[] arr, int start, int end)
{
    if (start >= end) return;

    int pivot = arr[end]; // 마지막 요소를 pivot으로 선택
    int leftPtr = start;
    int rightPtr = end - 1;

    while (leftPtr <= rightPtr)
    {
        while (leftPtr <= rightPtr && arr[leftPtr] <= pivot) ++leftPtr; // 왼쪽에서 pivot보다 큰 값을 찾는다
        while (leftPtr <= rightPtr && arr[rightPtr] >= pivot) --rightPtr; // 오른쪽에서 pivot보다 작은 값을 찾는다
        if (leftPtr < rightPtr) swap(arr, leftPtr, rightPtr); // 조건을 만족하면 swap
    }

    swap(arr, leftPtr, end); // pivot을 leftPtr 위치와 교환하여 pivot을 정확한 위치에 둔다

    // 분할된 두 구간에 대해 재귀적으로 정렬 수행
    v1(arr, start, leftPtr - 1);
    v1(arr, leftPtr + 1, end);
}

• 양쪽에서 접근하는 방식 (two-pointer approach)
• leftPtr은 왼쪽에서 오른쪽으로, rightPtr은 오른쪽에서 왼쪽으로 이동
• 두 포인터가 교차할 때까지 pivot보다 큰 값과 작은 값을 찾아 교환
• 코드가 간단하고 직관적

 

v2()

public static void v2(int[] arr)
{
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivot = partition(arr, low, high); // 피벗을 기준으로 배열을 분할하고 피벗의 최종 위치를 얻음
        quickSort(arr, low, pivot - 1); // 피벗을 기준으로 왼쪽 부분 정렬
        quickSort(arr, pivot + 1, high); // 피벗을 기준으로 오른쪽 부분 정렬
    }
}

private static int partition(int[] arr, int low, int high)
{
    int pivot = arr[high]; // 맨 오른쪽 요소를 피벗으로 선택
    int i = (low - 1); // i는 피벗보다 작은 요소들의 경계를 나타냄

    for (int j = low; j < high; ++j)
    {
        // 현재 요소가 피벗보다 작으면
        if (arr[j] < pivot)
        {
            i++;
            swap(arr, i, j); // arr[i]와 arr[j]를 교환
        }
    }

    // 피벗을 올바른 위치로 이동
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

• 단방향 스캔 방식 (single-scan approach)
• i는 작은 요소들의 경계를 표시
• j는 배열을 순차적으로 스캔
• pivot보다 작은 값을 발견할 때마다 경계를 확장하고 교환
• 구조가 더 모듈화되어 있음 (partition 메서드가 분리됨)