[JavaScript] 퀵 정렬

퀵 정렬 (Quick Sort)

퀵 정렬은 **분할 정복 알고리즘 (Divide and Conquer)**의 일종으로, 배열을 **"피벗"**을 기준으로 나누어 정렬하는 방식입니다.
다양한 효율적인 정렬 알고리즘 중에서 매우 빠른 성능을 자랑하며, 평균 시간 복잡도는 **O(nlog⁡n)O(n \log n)O(nlogn)**입니다.

---

동작 원리

1. 피벗 선택 (Pivot Selection):
   배열에서 임의의 요소를 피벗(pivot)으로 선택합니다.
2. 분할 (Partitioning):
   피벗을 기준으로, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 배치하여 배열을 두 개의 부분으로 나눕니다.
3. 재귀적 정렬 (Recursion):
   나눈 두 부분에 대해서 각각 퀵 정렬을 다시 수행합니다. 이 과정을 배열이 정렬될 때까지 반복합니다.
4. 병합 (Merge):
   퀵 정렬은 분할 정복 방식에서 병합이 따로 필요하지 않습니다. 각 부분 배열이 독립적으로 정렬되기 때문에 자동으로 정렬이 완료됩니다.

---

장단점

• 장점:
  • 평균적으로 매우 빠르다: 평균 시간 복잡도가 O(nlog⁡n)O(n \log n)O(nlogn)으로 매우 효율적입니다.
  • 공간 효율성: 퀵 정렬은 **제자리 정렬 (In-Place Sort)**로, 추가적인 배열을 만들지 않고 배열을 직접 수정하기 때문에 공간을 적게 사용합니다.
• 단점:
  • 최악의 경우 O(n2)O(n^2)O(n2): 피벗을 잘못 선택하면 분할이 불균형하게 이루어져 시간 복잡도가 O(n2)O(n^2)O(n2)로 나빠질 수 있습니다.
  • 불안정한 정렬 (Unstable Sort): 동일한 값의 순서가 바뀔 수 있습니다.
• 적합한 경우:
  • 데이터가 큰 경우, 평균적으로 빠른 성능을 보이는 정렬 알고리즘입니다.

---

퀵 정렬 구현 (JavaScript)

const quickSort = (array) => {
  // 배열의 크기가 1 이하라면 이미 정렬된 배열
  if (array.length <= 1) return array;

  // 피벗을 선택 (여기서는 배열의 첫 번째 요소)
  const pivot = array[0];
  const left = [];
  const right = [];

  // 피벗을 기준으로 배열 나누기
  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }

  // 재귀적으로 왼쪽과 오른쪽을 퀵 정렬하고, 피벗과 합침
  return [...quickSort(left), pivot, ...quickSort(right)];
};

const an = [5, 1, 4, 2, 8];
console.log(quickSort(an)); // [1, 2, 4, 5, 8]

 

퀵 정렬 동작 예시

배열: [5, 1, 4, 2, 8] (오름차순 정렬)

1단계 (피벗 선택 및 분할)

• 피벗: 5
• 피벗을 기준으로 배열을 나누기:
  • 왼쪽 배열 (피벗보다 작은 값): [1, 4, 2]
  • 오른쪽 배열 (피벗보다 큰 값): [8]

2단계 (왼쪽 배열에 대한 퀵 정렬)

• 피벗: 1
• [1, 4, 2]를 정렬:
  • 피벗을 기준으로 나누기:
    • 왼쪽 배열: []
    • 오른쪽 배열: [4, 2]
• [4, 2]에서 피벗: 4로 정렬:
  • 피벗을 기준으로 나누기:
    • 왼쪽 배열: [2]
    • 오른쪽 배열: []

3단계 (결과 병합)

• 왼쪽: [1] + [2, 4] → [1, 2, 4]
• [1, 2, 4]와 피벗 5, [8]을 합치면 → [1, 2, 4, 5, 8]

---

시간 복잡도

• 최선 및 평균 경우: O(nlog⁡n)O(n \log n)O(nlogn)
  • 피벗을 적절히 선택하면 각 분할에서 nnn번의 비교가 필요하고, 분할 깊이는 log⁡n\log nlogn입니다.
• 최악의 경우: O(n2)O(n^2)O(n2)
  • 피벗을 최댓값 또는 최솟값으로 선택하는 경우, 배열이 매우 불균형하게 나누어져 nnn번의 비교와 nnn번의 분할이 필요합니다.
• 공간 복잡도: O(log⁡n)O(\log n)O(logn)
  • 재귀 호출에 의해 발생하는 호출 스택 때문에 공간 복잡도는 O(log⁡n)O(\log n)O(logn)입니다. 추가적인 배열을 사용하지 않아서 공간 효율적입니다.

---

한 줄 요약

퀵 정렬은 피벗을 기준으로 배열을 나누어 정렬하는 알고리즘으로, 평균적으로 빠르고 공간 효율적입니다. 최악의 경우 O(n2)O(n^2)O(n2)의 성능을 가질 수 있지만, 평균적으로는 매우 빠른 정렬입니다. 😊