퀵 정렬

피벗(pivot)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하며 재귀적으로 정렬하는 알고리즘입니다.

동작 과정

[5, 3, 8, 1, 2]  pivot = 5

partition:
  3 < 5 → 왼쪽
  8 > 5 → 오른쪽
  1 < 5 → 왼쪽
  2 < 5 → 왼쪽

→ [3, 1, 2] | 5 | [8]

재귀:
[3, 1, 2] → pivot=3 → [1, 2] | 3 → [1, 2, 3]
[8]       → 단일 원소

결과: [1, 2, 3, 5, 8]

구현

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = partition(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
}

int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[right]; arr[right] = tmp;
    return i + 1;
}

복잡도

• 불안정 정렬 X
• in-place O
• 평균적으로 병합 정렬보다 빠름 (캐시 효율)
• 최악 방지: 랜덤 피벗 또는 median-of-three 전략 사용

→ 정렬