[알고리즘] quick sort

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴한다.

arr.sort 사용은 금지되며 퀵 정렬을 사용해서 해결해야 한다.

advanced 조건은 'quickSort 함수의 두 번째 인자로 callback 함수를 받아서, 그 함수의 리턴값을 기준으로 요소들을 정렬'하라는 것이다.

퀵 정렬은 분할 알고리즘 중 하나로 리스트 내에 있는 한 요소를 피벗(Pivot)이라고 정한다.
피벗을 기준으로 피벗보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 옮긴다.
이제 옮겨진 왼쪽 배열과 오른쪽 배열을 위와 같은 방법으로 다시 정렬한다.
이렇게 부분 배열이 더이상 분할이 되지 않을 때까지 반복한다.

처음 퀵 정렬을 보고 문제를 다시 보니 아무래도 재귀를 이용해야겠다는 생각이 들었다.
탈출 조건이 위 '부분 배열이 더이상 분할이 되지 않을 때'가 될 것이고, pivot 변수에는 arr[0]을 담고, smaller, bigger 변수를 만들어서 둘에는 각각 빈 배열을 담았다.

const quickSort = function (arr,transform = (item)=> item) {
  
  if(arr.length < 2){
    return arr;
  }//탈출조건 : 정렬해야 할 배열의 길이가 0이나 1이면 정렬할 필요가 없으므로 리턴한다. 

  let pivot = arr[0];
  const smaller = [];//왼쪽 배열 
  const bigger = [];//오른쪽 배열
  for(let i=1;i<arr.length;i++){
    
    if(transform(arr[i])>transform(pivot)){
      bigger.push(arr[i])
    }else{
      smaller.push(arr[i])
    }
  }
  const biggerSorted = quickSort(bigger,transform);
  const smallerSorted = quickSort(smaller,transform)
  
  return [...smallerSorted,pivot,...biggerSorted]
};