daily 알고리즘 : mergeSort

소히·2022년 7월 18일

MergeSort 알고리즘

알고리즘Daily

목록 보기

4/22

mergeSort

문제

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

입력

인자 1 : arr

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

출력

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

주의사항

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

입출력 예시

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

풀이

분할 -> 정복 -> 결합

분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
배열을 계속 2개의 부분배열로 나누는 작업을 배열에 하나의 원소만 남을때까지 반복한다.
두 개의 배열(left,right)을 값을 비교하여 작은 값을 sortedArr에 넣어주고 마지막에 3개의 배열을 합쳐준다.

function merge(left, right) {
  // 병합하는 함수
  const sortedArr = [];
  while (left.length && right.length) {
    // 2개의 배열을 첫번째 인덱스부터 비교하여 더 작은값을 sortedArr로 push해준다.
    // 두 배열 중 length가 0이 될 때까지 반복한다.
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  // sortedArr배열에 남은 두 배열 값들을 더해준다.
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  // 분할하는 함수
  if (arr.length === 1) return arr;
  // 반으로 나누는 작업을 반복한다.
  const middle = Math.ceil(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}