문제 : mergeSort

mergeSort를 구현하세요

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

문제의 접근

잊을만 하면 나오는 정렬 문제다 이번에 할 정렬은 합병 정렬이다. 이 문제는 '컴퓨터과학로드맵'에서 한번 개념을 잡은 적이 있어서 쉽게 풀수 있을 것 같다.

1. 배열을 두 개로 나눈다.
2. 나누어진 두 배열을 각각 정렬한다.
3. 정렬된 두 배열을 합친다.

const mergeSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length === 1) {
    return arr // 배열이 1개면 그대로 반환
  }
  let half = Math.floor(arr.length/2);
  
  let one = mergeSort(arr.slice(0, half)); //배열 나눈거 1개
  let two = mergeSort(arr.slice(half)); // 또 다른 배열 1개
  
  return merge(one, two); // 병합한 배열을 리턴해준다.
};

이제 여기서 merge만 잘 만들어 주면 된다.

const merge = (one, two) => {
    var result = [];
    while (one.length && two.length) {
      if (one[0] <= two[0]) {
        result.push(one.shift());
      } else {
        result.push(two.shift());
      }
    }
    while (one.length) result.push(one.shift());
    while (two.length) result.push(two.shift());
    return result;  
  }

여기서 조금 오래 걸렸다. 삽질을 엄청 많이 했다.ㅜㅜㅜㅜ

문제를 통해 생각해 볼 것

다행히 개념을 어느 정도 아는 문제라서 무난하게 해결할 수 있었다. 이제 정렬은 다 한 것 같다...ㅜㅜ

Reference

const merge = function (left, right) {
  let merged = [];
  let leftIdx = 0,
    rightIdx = 0;
  const size = left.length + right.length;

  for (let i = 0; i < size; i++) {
    if (leftIdx >= left.length) {
      merged.push(right[rightIdx]);
      rightIdx++;
    } else if (rightIdx >= right.length || left[leftIdx] <= right[rightIdx]) {
      merged.push(left[leftIdx]);
      leftIdx++;
    } else {
      merged.push(right[rightIdx]);
      rightIdx++;
    }
  }

  return merged;
};

const mergeSort = function (arr) {
  if (arr.length < 2) return arr;
  const middle = parseInt(arr.length / 2);
  const left = mergeSort(arr.slice(0, middle));
  const right = mergeSort(arr.slice(middle));
  const merged = merge(left, right);
  return merged;
};