---

퀵정렬(Quick Sort) 완벽 이해: 개념부터 구현까지

정렬 알고리즘은 컴퓨터과학에서 가장 기본적이면서도 중요한 주제 중 하나입니다. 그중에서도 퀵정렬(Quick Sort)은 평균적으로 매우 빠른 성능을 보여 실제로 자주 사용되는 정렬 알고리즘입니다. 이번 글에서는 퀵정렬의 개념, 동작 원리, 시간복잡도, 장단점, 그리고 자바스크립트 구현까지 모두 살펴보겠습니다.

---

1. 퀵정렬(Quick Sort)란?

퀵정렬은 분할 정복(Divide and Conquer) 방법을 사용하는 정렬 알고리즘입니다.
간단히 말하면:

1. 리스트에서 하나의 기준 값(pivot)을 선택합니다.
2. 기준 값보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 분할(partition) 합니다.
3. 분할된 왼쪽과 오른쪽 리스트에 대해 재귀적으로 퀵정렬을 수행합니다.
4. 더 이상 나눌 수 없을 때, 모든 부분 리스트를 합쳐 최종 정렬 결과를 얻습니다.

퀵정렬은 제자리 정렬(in-place sort)이 가능하지만, 구현 방식에 따라 추가 배열을 사용하는 경우도 있습니다.

---

2. 퀵정렬 동작 예시

예를 들어 [3, 6, 2, 7, 5]를 정렬한다고 해봅시다.

1. 기준 값 선택: 5를 pivot으로 선택

2. 분할(partition):

   • 왼쪽: [3, 2] (5보다 작은 값)
   • 기준값: [5]
   • 오른쪽: [6, 7] (5보다 큰 값)

3. 왼쪽 재귀 호출: [3, 2] → pivot = 2 → [2], [3]

4. 오른쪽 재귀 호출: [6, 7] → pivot = 7 → [6], [7]

5. 합치기: [2, 3, 5, 6, 7]

이 과정을 통해 원래 배열이 정렬됩니다.

---

3. 퀵정렬 시간 복잡도

퀵정렬은 선택한 pivot에 따라 성능이 달라집니다.

경우	시간복잡도	설명
평균	O(n log n)	pivot이 적절하게 분할될 때
최악	O(n²)	pivot이 매번 최솟값이나 최댓값일 때
최선	O(n log n)	pivot이 항상 중앙값일 때

공간복잡도는 재귀 호출 때문에 O(log n)입니다(제자리 정렬 기준).

---

4. 퀵정렬 장단점

장점

• 평균적으로 매우 빠른 정렬 알고리즘
• 메모리 사용이 효율적(제자리 정렬 가능)
• 분할 정복 구조로 이해하기 쉬움

단점

• 최악의 경우 O(n²) 발생
• 안정 정렬(stable sort)이 아님 → 동일한 값의 상대적 순서 보장 X
• 재귀 호출로 인해 스택 오버플로우 가능 (리스트가 매우 길 경우)

---

5. 퀵정렬 구현 (JavaScript 예제)

function quickSort(arr) {
  if (arr.length <= 1) return arr; // 더 이상 나눌 수 없으면 반환

  const pivot = arr[arr.length - 1]; // 마지막 원소를 pivot으로 선택
  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)];
}

// 테스트
const nums = [3, 6, 2, 7, 5];
console.log(quickSort(nums)); // [2, 3, 5, 6, 7]

위 코드는 간단하고 직관적이지만, 추가 배열을 사용하기 때문에 제자리 정렬이 아닙니다.
제자리 정렬을 위해서는 배열 내부에서 swap을 이용한 partition 방식이 필요합니다.

---

6. 마무리

퀵정렬은 빠른 평균 성능과 분할 정복 구조 덕분에 실제 현업에서도 자주 사용되는 정렬 알고리즘입니다.
단, pivot 선택에 따라 성능 차이가 크므로, 실무에서는 랜덤 pivot 선택이나 3중 중앙값(Median-of-Three) 방식을 사용해 최악의 경우를 피하는 전략을 씁니다.

---

퀵정렬을 완전히 이해하면 재귀 구조, 분할 정복, 배열 조작을 모두 학습할 수 있어, 다른 알고리즘 공부에도 큰 도움이 됩니다.

---