[알고리즘/javascript]quickSort

문제

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

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length는 100,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 퀵 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

Advanced

• quickSort 함수의 두 번째 인자로 callback 함수를 받아서, 그 함수의 리턴값을 기준으로 요소들을 정렬해 보세요.

 

코드

naive solution

const quickSort = function (arr) {
  // 리스트의 크기가 0 또는 1이 될 때까지 반복한다(더 이상 분할이 불가능 할 때까지)
  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]);
  }

  //분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
  const lSorted = quickSort(left);
  const rSorted = quickSort(right);
  return [...lSorted, pivot, ...rSorted];
};

Advanced solution

function quickSort(arr, transform = (item) => item) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const 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];
}