[JavaScript] 정렬 (4) 빠른 정렬

정의

빠른 정렬이란 기준점을 잡고 기준점의 대소를 기준으로 배열을 나누는 과정을 재귀적으로 반복해서 모든 항목을 정렬하는 방법이다.
아래는 빠른 정렬을 그림으로 도식화한 것이다.

빠른 정렬은 이진 탐색의 방법을 응용하기 때문에 시간 복잡도가 O(nlog(n))으로 줄어든다.
하지만 최악의 경우에는 시간복잡도가 O(n^2)로 늘어날 수도 있다.

코드

아래는 코드이다.

const quickSort = function (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]);
  }

  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};