퀵 정렬: 첫 피벗의 자리를 확정하고 양쪽을 정렬하기

퀵 정렬은 피벗 하나의 최종 위치를 먼저 확정합니다. 작은 값은 왼쪽으로, 크거나 같은 값은 오른쪽으로 나눈 뒤 피벗을 제외한 두 구간만 다시 처리합니다.

선수 지식: 재귀, 배열 구간, 값 교환, 정렬의 불변식

• 분할이 보장하는 것과 아직 보장하지 않는 것을 구분합니다.
• 첫 피벗이 정렬된 입력에서 만드는 최악의 분할을 이해합니다.
• 작은 구간만 재귀로 처리하여 호출 깊이를 제한합니다.

피벗보다 작은 값의 구간을 앞쪽에 모읍니다

[3, 1, 4, 2]에서 첫 값 3을 피벗으로 고릅니다. 피벗을 잠시 첫 자리에 두고 나머지를 왼쪽부터 봅니다. boundary는 지금까지 모은 작은 값 구간의 끝입니다. 새 값이 3보다 작으면 boundary를 한 칸 늘리고 그 자리와 새 값의 자리를 바꿉니다. 크거나 같은 값이면 작은 구간에 넣지 않고 다음 값으로 넘어갑니다.

스캔 도중에는 첫 자리 다음부터 boundary까지가 피벗보다 작은 구간입니다. boundary 다음부터 이미 살핀 자리까지는 피벗보다 크거나 같은 구간입니다. 아직 살피지 않은 뒤쪽은 어떤 순서라도 괜찮습니다. 작은 값을 새로 만나면 큰 구간 맨 앞과 교환하여 이 구분을 유지합니다. 한 번의 교환은 정렬 전체가 아니라 구간의 조건을 지키는 동작입니다.

스캔이 끝나면 첫 자리의 피벗을 boundary와 바꿉니다. 왼쪽에는 모두 작은 값, 오른쪽에는 모두 크거나 같은 값이 있으므로 피벗은 최종적으로 들어갈 한 위치에 놓입니다. 양쪽 구간 안의 순서는 아직 섞여 있을 수 있어 각각 정렬해야 합니다. 병합 정렬과 달리 두 결과를 다시 합치는 별도 병합 단계는 없습니다.

작은 값의 경계를 움직인 뒤 피벗을 놓습니다

분할 뒤 [2, 1]은 여전히 정렬되지 않았지만 둘 다 3보다 작습니다. 이 구간만 같은 방식으로 정렬하면 [1, 2]가 됩니다. 오른쪽 [4]는 한 원소라 추가 작업이 없습니다. 피벗 인덱스를 다음 구간에 다시 포함하지 않아야 매번 문제 크기가 줄어듭니다.

첫 피벗의 최악 시간과 호출 깊이를 구분합니다

이미 정렬된 [1, 2, 3, 4]에서 첫 피벗 1보다 작은 값은 없습니다. 분할 뒤 왼쪽은 비고 오른쪽에 3개가 남습니다. 다음에도 같은 일이 반복되어 비교 수가 3 + 2 + 1이 됩니다. 역순이나 같은 값만 있는 배열에서도 이 분할 방식은 불균형해질 수 있어 최악 시간은 O(n²)입니다. 첫 값을 고정해서 고르는 코드에 항상 빠르다는 보장은 없습니다.

양쪽을 모두 그대로 재귀 호출하면 이런 입력에서 깊이도 O(n)이 되어 호출 스택 한계에 부딪힐 수 있습니다. 예제는 양쪽 길이를 비교하여 작은 쪽만 재귀 호출하고 큰 쪽은 while문으로 이어갑니다. 재귀로 내려가는 구간은 직전 구간의 절반 이하라 동시에 살아 있는 호출 깊이는 O(log n)으로 제한됩니다. 빈 구간이나 한 원소는 바로 끝납니다.

이 변경은 스택 사용을 줄여도 최악 비교 수를 줄이지는 않습니다. 큰 구간을 반복문으로 처리하더라도 n – 1, n – 2 크기의 스캔을 계속 해야 하기 때문입니다. 평균 O(n log n)은 원소가 서로 다른 임의 순서의 입력처럼 피벗 순위가 골고루 나타나는 가정에서 말합니다. 중복이 많은 입력에는 삼방향 분할, 보장된 시간에는 다른 정렬 전략을 고려할 수 있습니다.

숫자 계약과 실제 사용하는 공간을 확인합니다

함수는 빈 칸 없는 유한 Number 배열만 받아 복사본을 오름차순으로 정렬합니다. 빈 배열·한 원소·음수·중복값을 허용하며 원본은 바꾸지 않습니다. NaN은 크다·작다 비교가 모두 거짓이라 숫자 정렬의 기준으로 삼기 어려우므로 길이 1일 때도 거절합니다. 입력 검사는 분할이 시작되기 전에 하며, 길이가 작다고 잘못된 원소 검사를 생략하지 않습니다.

원본 보존용 복사본이 O(n), 작은 구간 재귀의 호출 스택이 O(log n)이므로 반환 결과를 포함한 추가 공간은 O(n)입니다. 분할 과정은 인덱스와 임시 교환 값만 사용하며 별도 부분 배열을 만들지 않습니다. 멀리 떨어진 값들을 교환하기 때문에 같은 키의 원래 순서를 보장하는 안정 정렬은 아닙니다. 동률 순서가 필요한 문제에서는 이를 입력 계약에 맞춰 선택해야 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function copyFiniteNumbers(values) {
  if (!Array.isArray(values)) throw new TypeError('숫자 배열이 필요합니다.');
  for (let i = 0; i < values.length; i++) {
    if (!Object.hasOwn(values, i) || !Number.isFinite(values[i])) {
      throw new TypeError('빈 칸 없는 유한 숫자 배열이 필요합니다.');
    }
  }
  return values.slice();
}

function quickSort(values) {
  const a = copyFiniteNumbers(values);
  function swap(i, j) {
    [a[i], a[j]] = [a[j], a[i]];
  }
  function partition(left, right) {
    const pivot = a[left];
    let boundary = left;
    for (let i = left + 1; i <= right; i++) {
      if (a[i] < pivot) {
        boundary++;
        swap(boundary, i);
      }
    }
    swap(left, boundary);
    return boundary;
  }
  function sort(left, right) {
    while (left < right) {
      const pivotIndex = partition(left, right);
      if (pivotIndex - left < right - pivotIndex) {
        sort(left, pivotIndex - 1);
        left = pivotIndex + 1;
      } else {
        sort(pivotIndex + 1, right);
        right = pivotIndex - 1;
      }
    }
  }
  sort(0, a.length - 1);
  return a;
}

const input = [3, 1, 4, 2];
console.log(JSON.stringify(quickSort(input)));
console.log(JSON.stringify(input));
console.log(JSON.stringify(quickSort([2, -1, 2, 0])));

node javascript-quick-sort-first-pivot.mjs

[1,2,3,4]
[3,1,4,2]
[-1,0,2,2]

비용과 적용 범위

시간: 최선 O(n log n), 평균 O(n log n), 최악 O(n²)

공간: O(n), 반환 복사본 제외 호출 스택 O(log n)

분석 조건: 첫 원소 피벗과 경계 인덱스로 작은 값 구간을 모으는 분할입니다. 평균은 서로 다른 키가 임의 순서인 가정이며, 정렬된 입력·역순·모두 같은 값에서 최악이 가능합니다. 작은 쪽만 재귀로 처리하여 최악 시간과 별개로 스택 깊이를 제한합니다.

직접 확인해 보기

[2, 3, 1]에서 첫 피벗 2로 한 번 분할하면 피벗은 어느 인덱스에 놓이나요? 양쪽 구간에는 무엇이 남나요?

함께 읽을 글

• 이진 탐색의 불변식: 탐색 구간·중간값·종료 조건 — 구간 경계가 줄어드는 조건과 종료의 관계를 비교합니다.
• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 원본 보존용 복사와 제자리 분할 작업의 비용을 구분합니다.

참고 자료

• Princeton Algorithms — Quicksort — 피벗 분할, 평균과 최악 시간, 불균형 분할 및 중복 키의 영향을 참고했습니다. 예제는 첫 피벗의 경계 스캔과 작은 구간 재귀 방식으로 직접 구성했습니다.