빠르지만 까칠한 천재

크리스는 합병 정렬(Merge Sort)의 속도(O(N log N))에 감탄했지만, 한 가지 불만이 남았다.

"속도는 빠른데, 배열을 자꾸 새로 만드니까(Slice) 메모리를 너무 많이 써. 메모리 공간은 안 쓰면서 속도는 그대로인 알고리즘은 없을까?"

그때 시니어 개발자가 말했다.

"그래서 실무에서는 퀵 정렬(Quick Sort)을 많이 쓰지. 이 녀석은 이름값 하는 천재야. 평균적으로 가장 빠르거든. 하지만 성격이 좀 까칠해서 다루기 조심해야 해."

도대체 어떤 점이 '까칠하다'는 걸까? 오늘은 정렬 알고리즘의 표준이자 가장 널리 쓰이는 퀵 정렬을 파헤쳐 본다.

1. 피벗(Pivot): "나를 기준으로 헤쳐 모여!"

합병 정렬이 "일단 반으로 쪼개고 나중에 정렬(합병)하자"는 주의라면,

퀵 정렬은 "기준(Pivot)을 하나 잡고, 걔보다 작은 건 왼쪽, 큰 건 오른쪽으로 몰아넣자"는 주의다.

동작 과정

배열 [5, 2, 1, 8, 4, 7, 6, 3]이 있다고 치자.

2. 자바스크립트로 구현하기 (In-place)

퀵 정렬의 진가는 추가 메모리를 거의 쓰지 않고(In-place), 원본 배열 안에서 위치만 샥샥 바꾸는 데 있다. 이를 위해 '피벗 도우미(Partition Helper)' 함수를 먼저 만든다.

1) Partition 함수

이 함수는 피벗보다 작은 값들을 왼쪽으로 몰아넣고, 피벗이 위치해야 할 최종 인덱스를 반환한다.

function pivot(arr, start = 0, end = arr.length - 1) {
  // 편의상 맨 앞 요소를 피벗으로 설정
  let pivotValue = arr[start];
  let swapIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivotValue > arr[i]) {
      swapIdx++;
      // 피벗보다 작은 값을 발견하면, swapIdx 위치의 값과 교환해서 앞으로 땡겨온다.
      [arr[swapIdx], arr[i]] = [arr[i], arr[swapIdx]];
    }
  }

  // 마지막으로 피벗을 자신의 진짜 위치(swapIdx)로 이동시킨다.
  [arr[start], arr[swapIdx]] = [arr[swapIdx], arr[start]];
  
  return swapIdx; // 피벗의 최종 인덱스 반환
}

2) QuickSort 함수

이제 재귀를 이용해 전체 로직을 완성한다.

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 1. 피벗을 제자리에 두고, 그 위치(index)를 받아온다.
    let pivotIndex = pivot(arr, left, right);

    // 2. 피벗 기준 왼쪽 부분 정렬
    quickSort(arr, left, pivotIndex - 1);

    // 3. 피벗 기준 오른쪽 부분 정렬
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

quickSort([4, 8, 2, 1, 5, 7, 6, 3]);

3. 성능 분석: 왜 '까칠한 천재'인가?

장점: 평균적인 속도왕 (O(N log N))

단점: 최악의 시나리오 (O(N^2))

이것이 퀵 정렬이 '까칠한' 이유다.

만약 이미 정렬된 배열 [1, 2, 3, 4, 5]에 대해 맨 앞(1)을 피벗으로 잡으면 어떻게 될까?

배열이 반으로 쪼개지지 않고, 한 개씩만 줄어든다. 이러면 깊이가 N만큼 깊어져서 버블 정렬(O(N^2))과 똑같이 느려진다.

해결책: 피벗을 맨 앞이 아니라 랜덤(Random)하게 고르거나, 중간값(Median)을 고르면 이 문제를 99% 해결할 수 있다.

4. 합병 정렬 vs 퀵 정렬 비교

핵심 정리

지금까지 배운 정렬들은 모두 데이터를 "비교(Comparison)"해서 정렬했다.

그런데 트리(Tree) 구조를 이용하면, 최솟값이나 최댓값을 기가 막히게 빨리 뽑아낼 수 있다.

이진 힙(Binary Heap)이라는 자료구조를 활용한 우아한 정렬법, 힙 정렬(Heap Sort)을 만나보자.

🔗 참고 링크