Algorithm problem-16

1. 문제

• 퀵 정렬로 배열을 정렬해서 리턴

2. 시도

• 퀵 정렬의 개념을 구글링으로 공부한 후, 개념은 이해했으나 코드로 옮기는 능력이 부족
• 다른 언어의 코드를 보아도, 이번 건 이해가 전혀 안되어 애를 먹었음
• JAVA에 적용한 방법을 보고, 참고삼아 코드를 작성하였음
• pivot점을 두고 작은건 앞, 큰건 뒤로 모아, 각자 재귀시켜서
• 각 배열을 합산하여 리턴시키는 방법
• 시간복잡도 해결을 위한 콜백함수의 리턴값 적용을 못하였음

3. 수도코드

const quickSort = function (arr, callback = (n) => n) {
  // base case
  if (arr.length <= 1) return arr;
  // recursive case
  // [arr[Math.floor(arr.length / 2)]] // mid로 하려니 반복문 돌리기 애매해진다
  let pivot = [arr[0]] // 0인덱스를 기준으로 정해보자
  let front = []; // 작은 애들은 앞으로 모으고
  let rear = []; // 큰 애들은 뒤로 모아보자
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      front.push(arr[i]);
    }
    else if (arr[i] >= pivot) {
      rear.push(arr[i]);
    }
  }
  return quickSort(front).concat(pivot, quickSort(rear));
};
// pivot을 두고, 작으면 앞, 크면 뒤로 모아서 다시 또 앞과 뒤를 pivot을 정해서 재귀로 진행
// base case를 길이가 1이 될 때까지로 정하고 돌리면 될 듯

4. 레퍼런스

const quickSort = function (arr, callback = (n) => n) {
  // base case
  if (arr.length <= 1) return arr;
  // recursive case
  let pivot = arr[0];
  let front = [];
  let rear = [];
  for (let i = 1; i < arr.length; i++) {
    if (callback(arr[i]) <= callback(pivot)) {
      front.push(arr[i]);
    }
    else if (callback(arr[i]) > callback(pivot)) {
      rear.push(arr[i]);
    }
  }
  let frontSort = quickSort(front, callback);
  let rearSort = quickSort(rear, callback);
  return frontSort.concat(pivot, rearSort);
};