문제 : quickSort

배열을 입력받아 오름차순으로 정렬하여 리턴하는 함수

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

문제의 접근

이번 정렬 방식은 퀵 정렬이다. 문제 풀면서 정렬이랑 정렬은 전부 구현할 것 같다. 그렇다면 먼저 퀵정렬이 뭔지를 먼저 알아보자.

불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬

이 정렬은 최악의 경우 O(n^2)의 복잡도를 가지는데 평균적으로 O(n logn)의 복잡도를 가진다고 한다.

위 그림이 딱 퀵 정렬을 요약해둔 것과 같다. 하지만 단순히 동작하는 모습만 보고 코드를 작성한다면 그건 천재겠지... 난 천재가 아니라서 예시가 필요했다.

다음 배열 [3,7,8,5,2,1,9,5,4]를 예로 들어서 설명해보자.

• 특정 pivot을 하나 지정해준다. 이 문제에서는 5를 지정해주자.
• 특정 피봇을 대상으로 피봇보다 큰 수를 왼쪽left에 넣어주고 큰 수를 right에 넣어준다.
• [...left, pivot, ...right]를 통해서 다시 원래의 배열로 만들어 준다.

다음 과정을 시행하면 pivot을 대상으로 작은수들은 왼쪽에 큰 수들은 오른쪽에 정렬되기 때문에 다른 수는 몰라도 해당 pivot의 위치는 확정되게 된다.

이제 이 사이클을 left와 right에 계속해서 적용해 나간다면 최종적으로 우리가 원하는 퀵 정렬이 완성된다.

const quickSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length < 2){ // 재귀함수의 탈출 조건
    return arr
  } 
  
  let pivot = [arr[0]]; // pivot 이 담긴 배열
  let left = []; // pivot 보다 작은 수가 담길 배열
  let right = []; // pivot 보다 큰 수가 담길 배열

  for(let i = 1; i < arr.length; i++){ //pivot을 제외한 모든 값들을 조회
    if(arr[i] < pivot){ // 비교하여 left 혹은 right에 담기
      left.push(arr[i])
    } else if(arr[i] > pivot){
      right.push(arr[i])
    }else{
      pivot.push(arr[i])
    }
  }
  // 재귀를 통해서 정렬된 값들을 붙여서 반환해준다.
  return quickSort(left).concat(pivot, quickSort(right))
};

위 코드로 간단하게 구현할 수 있지만 이 코드의 경우 메모리를 많이 차지한다고 한다. 때문에 우리는 이보다 더 효율적으로 코드를 작성해야 한다.

const quickSort = function (arr, left = 0, right = arr.length - 1, callback = (num) => num) {
  // TODO: 여기에 코드를 작성합니다.

  const div = (arr, left, right, pivot) => {
    while(left <= right){
      while(arr[left] < pivot){
        left++;
      }

      while(arr[right] > pivot){
        right--;
      }

      if(left <= right){
        let temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
      }
    }
    return left;
  }

  if(left < right){
    const mid = Math.floor((left+right)/2);
    const pivot = arr[mid];
    const partition = div(arr, left, right, pivot);

    quickSort(arr, left, partition-1);
    quickSort(arr, partition, right);
  }
  return arr
};

다음 코드는 처음 설명한 코드와 같은 메커니즘을 가지고있지만 메모리 효율에 있어서 더 우위를 가지고있는 코드다.

Advanced

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

이 문제 또한 퀵 정렬만 잘 구현했다면, 문제없이 해결 가능하다. 값을 비교시 인자로 받은 콜백함수를 적용해서 비교해주면 된다.

const quickSort = function (arr, callback = (num) => num, left = 0, right = arr.length - 1) {
  // TODO: 여기에 코드를 작성합니다.

  const div = (arr, left, right, pivot) => {
    while(left <= right){
      while(callback(arr[left]) < callback(pivot)){
        left++;
      }

      while(callback(arr[right]) > callback(pivot)){
        right--;
      }

      if(left <= right){
        let temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
      }
    }
    return left;
  }

  if(left < right){
    const mid = Math.floor((left+right)/2);
    const pivot = arr[mid];
    const partition = div(arr, left, right, pivot);

    quickSort(arr,callback, left, partition-1);
    quickSort(arr,callback, partition, right);
  }
  return arr
};

이 코드를 작성하면서 주의해야 할 점이 몇가지 있다.

• 콜백 함수에 기본인자 전달
• 재귀 함수에 들어가는 인자에도 콜백 함수 전달
• 인자 전달 순서

이 3가지를 신경쓰지 않고 했다가 문제 다 풀어두고 3시간이나 고민했다...

문제를 통해 생각해 볼 것

문제의 reference는 다음과 같다.

// naive solution
// const quickSort = function (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]);
//   }

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

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];
}

말이 안나올 정도로 간단하고 가독성 또한 뛰어나다... 이번에도 퀵 정렬을 코드를 작성하면서 겨우 이해할 수 있었다. 진짜 획기적인 방법이 많은 듯 하다. 어떻게 이런 것들을 생각해내는지... 세상 천지에 천재들이 넘쳐 흐르는 듯 하다😢

다시보니 처음 코드에서 꼬리재귀를 통해 메모리를 절약해준게 reference다... 진짜 멍청한 짓을 한 것 같다.