Quick Sort

pviot(중심축)을 정하고 중심축 보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 보낸다. 이렇게 재귀적으로 pivot을 정해서 왼쪽 오른쪽을 나눠서 부분 리스트의 합이 전체 리스트가 되게 하는 방법이다.

Divde and Conquer 알고리즘에 속한다.

 

big O

O(nlogn)

 

 

const quickSort = function (arr, transform =(item)=> item) {
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length<2){
    return arr;
  }

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

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