3.6Quick Sort

Quick Sort

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다. 배열에서 하나의 요소를 피벗(pivot)으로 선택하고, 나머지 요소들을 피벗보다 작거나 큰 값으로 나누어 각각 재귀적으로 정렬한다.

1. 배열의 첫 요소보다 작은 요소는 왼쪽으로, 큰 요소들은 오른쪽으로 보낸다. 첫 요소는 피벗이 되어 올바른 위치에 정렬된다.
2. 피벗의 왼쪽에 있는 요소들로 구성된 배열 및 오른쪽에 있는 요소들로 구성된 배열에 대해 1을 재귀적으로 적용한다.

---

피벗(Pivot) 요소 선택 구현하기

우선, 배열의 첫 요소를 피벗으로 선택하고, 해당 요소를 정렬되었을때 올바른 인덱스로 보내고 작은 요소들은 왼쪽으로, 큰 요소들을 오른쪽으로 보내는 pivot() 함수(Partition이라고도 불림)부터 구현해보자.

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

  let pivotValue = arr[start];
  let swapIdx = start;

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

  swap(arr, start, swapIdx);
  return swapIdx; // 피벗의 최종 위치
}

pivot([4, 8, 2, 1, 5, 7, 6, 3]); // 4
// 5 왼쪽에 4개 요소, 오른쪽에 3개 요소가 올 수 있다.

Quick Sort 구현

javascript
function quickSort(arr, left = 0, right = arr.length - 1){
  // Base Case: 퀵 정렬할 배열의 길이가 1인 경우까지 재귀적으로 반복
  if(left < right){
    let pivotIndex = pivot(arr, left, right);
    // 왼쪽 부분 정렬
    quickSort(arr, left, pivotIndex - 1);
    // 오른쪽 부분 정렬
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

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

Quick Sort의 Big O

Quick Sort는 최선의 경우 및 평균이 모두 시간 복잡도 O(n log n)이 걸린다. 우선 배열의 피벗을 올바른 위치에 배치하는게 n, 그리고 그렇게 선택된 피벗 요소를 기준으로 왼쪽과 오른쪽의 배열들을 나누는데 log n이 걸리기 때문이다.

하지만, 피벗이 최댓값/최솟값일때가 퀵 정렬 최악의 경우의 수인데, 이 경우 왼쪽/오른쪽 한쪽에 대해서만 배열을 계속 나눠가야하는데 이러면 O(n²)이 걸린다. 즉, 배열 종류에 따라 피벗을 잘 선택하는 것이 아주 중요하고, 피벗 선택이 좋지 않으면 성능이 크게 저하될 수 있다는 것을 이해하고 사용해야 한다.

반면 공간 복잡도는 재귀 호출 스택인 O(log n)이 드는데, 새로운 배열을 만들지 않고 제자리에서 정렬(in-place sort)하기 때문에 공간 복잡도가 낮은 편이다.