Toy 문제 20

문제

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

 

주의사항

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

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

 

 

수도코드(해석)

합병 정렬 또는 병합 정렬(merge sort)은 O(log n) 비교기반 정렬 알고리즘입니다.

 

 

분해하고

 

순서에 맞게 합친다

 

 

 

재귀 함수를 통해서 왼쪽 오른쪽을 계속해서 나누고,

값 비교를 통해서 result라는 변수에 순서대로 넣는방식으로 코드를 짰습니다. 설명은 주석에..

하지만 테스트를 돌렸을 때 조금 시간이 걸린것을 느꼈고 레퍼런스보다 효율이 낮다는 것을 느꼈습니다.

병합은 O(log n) 효율이 나와야 하는데 제가 짠 코드는 O(n) 시간 복잡도가 나오는 것 같습니다.

자료가 많으면 많을 수록 처리하기 힘들어지는..

 

그래서 제대로 된 코드는 레퍼런스로 짜여진 코드입니다. 

레퍼런스는 반복문을 한번만 사용하면서 그 하나의 반복문 안에서 동작을 처리해서 시간 복잡도가 적게 나오는 것 같습니다.

 

코드

const mergeSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  
  if(arr.length === 1) {
    return arr // 배열이 1개면 그대로 반환
  }
  
  
  let half = Math.floor(arr.length/2); // 배열의 길이 절반
  let left = mergeSort(arr.slice(0, half)); //배열 나눈 왼쪽
  let right = mergeSort(arr.slice(half)); // 배열 나눈 오른쪽
  // 재귀함수를 통해서 계속하여 나눔
  

  const merge = (left, right) => {
    var result = [];
    while (left.length && right.length) { // 크기를 비교해서 작은 값은 result에 주입
      if (left[0] < right[0]) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }
    }
    while (left.length) result.push(left.shift()); // result에 넣지 않는 값을 전부 넣음
    while (right.length) result.push(right.shift()); // result에 넣지 않는 값을 전부 넣음
    return result;  
  }
  
  return merge(left, right); // 병합한 배열을 리턴해준다.


};

 

Reference Code

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