제코베 JS 100제 / 52 / quick sort

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

  const pivot = arr[0];
  const left = [];
  const right = [];

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

  return quickSort(left).concat(pivot, quickSort(right));
}

const array = prompt("배열을 입력하세요")
  .split(" ")
  .map((n) => parseInt(n, 10));

console.log(quickSort(array));

---

위의 코드에선 pivot을 배열의 가장 첫번째 값으로 잡았지만, 중간값으로 잡는게 좋다고 한다.

quick sort는 정렬이 불필요한 배열이 들어와도 수행하게 되는데, 이 경우 최악의 경우로 O(n^2)의 시간 복잡도를 가지게 된다.

어떤 배열이 들어올지 미지수인 상태에서 quick sort를 구현하게 된다면, 그나마 최소나 최대값이 아닌 확률이 가장적은 중간값으로 pivot을 잡는것이다.