quicksort [ 퀵정렬 ] javascript 구현

로직

원소를 정하여(피봇을 정하여), 해당 원소보다 작은 수들과 큰 수들로 나눕니다.

그리고 차례대로 작은수들, 피봇, 큰 수를 차곡차곡 담으면 정렬이 됩니다.

워낙에 유명한 로직이라 자세한 설명은 VisuAlgo에서 그림을 보면서 이해하면 됩니다.

code

const arr = [5, 1, 2, 3, 3, 1, 4, 3, 10];

console.log(quickSort(arr));

function quickSort(numbers) {
  if (numbers.length <= 1) {
    return numbers.length === 1 ? numbers : [];
  }

  const left = [],
    right = [];
  const pivot = numbers[0];

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

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