퀵 정렬(Quick Sort)

References

이번 글은 아래 자료를 참고하여 작성하였습니다.
Insertion Sort on Khan Academy

const partition = function (array, startIdx, lastIdx) {
  let partitonedArr = array,
    partitonedArrStartIdx = startIdx,
    partitonedArrLastIdx = lastIdx;

  const createPartitionedArr = function (
    partitonedArr,
    partitonedArrStartIdx,
    partitonedArrLastIdx
  ) {
    let partitonedRightArrStartIdx = partitonedArr[partitonedArrStartIdx];

    partitonedArr[partitonedArrStartIdx] = partitonedArr[partitonedArrLastIdx];
    partitonedArr[partitonedArrLastIdx] = partitonedRightArrStartIdx;
  };

  let partitonedLeftArrStartIdx = partitonedArrStartIdx;
  for (let s = partitonedArrStartIdx; s < partitonedArrLastIdx; s++) {
    if (partitonedArr[s] <= partitonedArr[partitonedArrLastIdx]) {
      createPartitionedArr(partitonedArr, s, partitonedLeftArrStartIdx);
      partitonedLeftArrStartIdx++;
    }
  }

  createPartitionedArr(
    partitonedArr,
    partitonedArrLastIdx,
    partitonedLeftArrStartIdx
  );

  return partitonedLeftArrStartIdx;
};

const quickSort = function (array, startIdx, lastIdx) {
  if (startIdx < lastIdx) {
    let midIdx = partition(array, startIdx, lastIdx);
    quickSort(array, startIdx, midIdx - 1);
    quickSort(array, midIdx + 1, lastIdx);
  }
};

const array = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6];
quickSort(array, 0, array.length - 1);
console.log(array); // [ 2, 3, 5, 6, 7, 9, 10, 11, 12, 14 ]

quick sort는 배열 정렬의 기준값이 되는 pivot을 기준으로 pivot보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 정렬하는 알고리즘이다. 이때 pivot은 배열의 가장 마지막 값이다.
위 그림에서 pivot의 값은 6인데, 두 번째 줄을 보면 6보다 작은 값은 왼쪽 배열에, 큰 값은 오른쪽 배열에 담겼다. 6을 기준으로 나눈 두 배열에서 다시 끝 값을 pivot으로 삼아 똑같은 방식으로 각 배열의 값을 정렬한다.
merge sort와 같이 divide-and-conquer 방식으로 작동한다. merge sort에서는 combine 단계에서 정렬이 이뤄지는 반면, quick sort에서는 divide 단계에서 모든 작업이 이뤄진다.