퀵 정렬 (Quick Sort) 설명과 JavaScript 예제

퀵 정렬은 분할 정복(Divide and Conquer) 전략을 사용하는 매우 빠른 정렬 알고리즘입니다. 평균 시간 복잡도가 O(n log n)으로 빠르며, 실제 애플리케이션에서도 널리 사용됩니다. 핵심 아이디어는 피벗(pivot)을 기준으로 작은 값과 큰 값을 분할하고 재귀적으로 정렬하는 것입니다.

---

1. 동작 원리

1. 배열에서 피벗 값을 하나 선택
2. 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
3. 분할된 배열을 재귀적으로 퀵 정렬 수행
4. 정렬된 왼쪽 + 피벗 + 정렬된 오른쪽을 합쳐 최종 정렬

---

2. JavaScript 예제 - 오름차순 정렬

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([33, 10, 55, 71, 29, 3, 87]));
// [3, 10, 29, 33, 55, 71, 87]

• pivot: 기준값 (예제에선 마지막 요소)
• left: pivot보다 작은 값 저장
• right: pivot보다 크거나 같은 값 저장
• 재귀적으로 정렬한 결과를 합쳐 반환

---

3. 성능 분석

구분	시간 복잡도
최선의 경우	O(n log n)
평균	O(n log n)
최악의 경우	O(n²)

• 최악의 경우는 이미 정렬된 배열에서 잘못된 pivot 선택 시 발생
• 공간 복잡도: O(log n) (재귀 호출 스택 기준)
• 제자리 정렬 가능 (in-place quick sort 구현 시)

---

4. 퀵 정렬의 특징

• 평균적으로 매우 빠름
• 정렬 라이브러리에서 널리 사용됨
• 피벗 선택이 성능에 큰 영향을 미침 → 랜덤 피벗 또는 중앙값 등을 고려

---

마무리

퀵 정렬은 빠른 성능 덕분에 많은 환경에서 기본 정렬 알고리즘으로 채택되고 있습니다. 단, 최악의 경우를 방지하기 위해 랜덤 피벗, 하이브리드 정렬(예: Timsort) 등의 변형도 존재합니다.

실제로 Array.prototype.sort() 내부 구현도 대부분 퀵 정렬 기반이거나 이를 응용한 방식입니다.