Algorithm 26 : quickSort

설명

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

예시

let output = quickSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

생각

퀵정렬은 처음 값을 기준으로 값이 작으면 왼쪽배열에 값이 크다면 오른쪽배열에 배치한다.

풀이

const quickSort = function (arr,cb=(num)=>(num)) {
  // TODO: 여기에 코드를 작성합니다.
  //예외처리
  if(arr.length <=1){
    return arr
  }
  let left =[]
  let right =[]
  let pivot = arr[0]

  for(let i=1;i<arr.length;i++){
    if(cb(arr[i]) < cb(pivot)){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  const lSorted = quickSort(left)
  const rSorted = quickSort(right)
  return [...lSorted,pivot,...rSorted]
};

깨달은 점

기준점을 기준으로 left,right 배열을 만들었다.
여기서 재귀함수를 통해 left,right 배열을 각각 또 정렬해야 했다. 그러면 초기 pivot값을 기준으로 left,right 값들이 정렬되기 때문에 이를 구조분해 할당으로 입력하면 된다는 것을 알게 되었다.