[알고리즘] 퀵 정렬 (Quick Sort)

요약

분할 정복 알고리즘.
하나의 배열을 pivot을 기준으로 삼아 두 개의 부분으로 분할하여 한쪽은 pivot보다 작은 것들, 다른 쪽은 pivot보다 큰 것들로 정렬한 다음, 각 부분을 또 계속 분할하면서 정렬하는 방법.

• 병합 정렬과 같이 분할 정복 알고리즘이 기반이지만 다른 점은 병합 정렬은 하나의 리스트를 절반으로 나누어 분할 정복을 하는데, 퀵 정렬은 pivot의 값에 따라 pivot을 기준으로 나뉜 리스트의 길이가 다를 수 있기 때문에 비균등하게 나뉜다는 것이다.
• 일반적으로는 병합 정렬보다 퀵 정렬이 빠르다.

과정

시간 복잡도

• Best Case: O(n log n)

  • 주어진 데이터(n)들을 완전 분할하기까지 log n개의 호출이 생긴다.
  • 정렬 자체에 필요한 수행시간은 n
  • 따라서 n * log n

• Worst Case: O(n^2)

  • 이미 정렬이 완료된 배열이 주어질 경우, 계속 불균형하게 나누어지므로 n^2이다.
  • 개선을 위해 pivot을 다른 위치로 뽑아서 할 수 있지만 100퍼센트 방지는 안되므로 O(n^2)이 허용이 안된다면 다른 정렬 방법을 선택해야한다.

공간 복잡도

• O(logn)

장점

• 시간 복잡도가 O(nlogn)을 가지는 다른 정렬 알고리즘들 중 가장 빠르다.
• 배열 안에서 교환하므로 다른 메모리 공간을 필요로 하지 않는 제자리 정렬이다.

단점

• 불안정 정렬이다.
• 정렬된 배열에 한해서는 수행시간이 오래 걸린다.

코드 구현

const pivot = (arr, start = 0, end = arr.length - 1) => {
  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  let pivot = arr[start]; // 가장 왼쪽을 기준으로 함
  let pivotIdx = start;

  for (let i = start + 1; i <= end; i++) {
    if (pivot > arr[i]) {
      pivotIdx++;
      swap(arr, pivotIdx, i);
    }
  }
  swap(arr, start, pivotIdx);

  return pivotIdx;
};

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left < right) {
    let pivotIdx = pivot(arr, left, right);
    // pivot은 고정이기 때문에 pivot에 -1, +1
    quickSort(arr, left, pivotIdx - 1); // left
    quickSort(arr, pivotIdx + 1, right); // right
  }
  return arr;
};