퀵정렬 JS (quick sort)

quick

듣자마자 오 빠른녀석인가 싶었다.

최악의 경우가 아니라면

병합배열과 같은 nlogn이지만, 그보다 빠르다고 한다.

(하이퀄리티 nlogn..?)

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));