[JS 100] 51. merge sort를 만들어보자

이춘구·2022년 8월 22일
0

js100

목록 보기
1/24

문제

병합정렬(merge sort)은 대표적인 정렬 알고리즘 중 하나로 다음과 같이 동작합니다.

  1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
  2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
    출처 : 위키피디아

해결 방안

배열을 하위 배열로 나누고 하나의 요소가 담겨있는 배열은 정렬된 것으로 본다.
위 과정을 재귀로 반복한다.

const arr = [3, 5, 2, 6, 4, 1, 8, 7, 9];

function mergeSort(arr) {
  console.log("분할 할 배열", arr);
  // 배열의 길이가 0 또는 1이면 그대로 반환
  if (arr.length < 2) {
    console.log("반환한 배열", arr);
    return arr;
  }
  // 배열의 길이를 반으로 나눈 값을 내림하여 중간값으로 정한다.
  const mid = Math.floor(arr.length / 2);
  // 배열에서 시작값(0)부터 중간값까지 잘라서 좌측 배열로 정한다.
  const leftArr = arr.slice(0, mid);
  // 배열에서 중간값부터 마지막값까지 잘라서 우측 배열로 정한다.
  const rightArr = arr.slice(mid);

  console.log("좌측배열", leftArr, "우측배열", rightArr);

  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

// 중간값을 기준으로 나뉘었던 좌측배열과 우측배열을 정렬하여 병합하는 함수
function merge(leftArr, rightArr) {
  console.log("병합정렬 할 배열", leftArr, rightArr);
  // 정렬된 배열이 들어갈 배열을 선언한다.
  const sortedArr = [];

  // 좌측배열과 우측배열이 모두 존재하는 동안,
  while (leftArr.length && rightArr.length) {
    // 좌측배열 첫번째 요소가 우측배열의 첫번째 요소보다 작거나 같으면,
    if (leftArr[0] <= rightArr[0]) {
      // 좌측배열의 첫번째 요소를 정렬된 배열에 넣고,
      sortedArr.push(leftArr.shift());
    } else {
      // 그 반대라면 우측배열의 첫번째 요소를 정렬된 배열에 넣는다.
      sortedArr.push(rightArr.shift());
    }
  }
  
  console.log("병합정렬 된 배열", [...sortedArr, ...leftArr, ...rightArr]);
  
  // 정렬된 배열과 좌측배열, 우측배열의 남은 값을 하나의 배열로 만들어 반환한다.
  return [...sortedArr, ...leftArr, ...rightArr];
}

console.log(mergeSort(arr));
분할 할 배열 [ 3, 5, 2, 6, 4, 1, 8, 7, 9 ]
좌측배열 [ 3, 5, 2, 6 ] 우측배열 [ 4, 1, 8, 7, 9 ]
분할 할 배열 [ 3, 5, 2, 6 ]
좌측배열 [ 3, 5 ] 우측배열 [ 2, 6 ]
분할 할 배열 [ 3, 5 ]
좌측배열 [ 3 ] 우측배열 [ 5 ]
분할 할 배열 [ 3 ]
반환한 배열 [ 3 ]
분할 할 배열 [ 5 ]
반환한 배열 [ 5 ]
병합정렬 할 배열 [ 3 ] [ 5 ]
병합정렬 된 배열 [ 3, 5 ]
분할 할 배열 [ 2, 6 ]
좌측배열 [ 2 ] 우측배열 [ 6 ]
분할 할 배열 [ 2 ]
반환한 배열 [ 2 ]
분할 할 배열 [ 6 ]
반환한 배열 [ 6 ]
병합정렬 할 배열 [ 2 ] [ 6 ]
병합정렬 된 배열 [ 2, 6 ]
병합정렬 할 배열 [ 3, 5 ] [ 2, 6 ]
병합정렬 된 배열 [ 2, 3, 5, 6 ]
분할 할 배열 [ 4, 1, 8, 7, 9 ]
좌측배열 [ 4, 1 ] 우측배열 [ 8, 7, 9 ]
분할 할 배열 [ 4, 1 ]
좌측배열 [ 4 ] 우측배열 [ 1 ]
분할 할 배열 [ 4 ]
반환한 배열 [ 4 ]
분할 할 배열 [ 1 ]
반환한 배열 [ 1 ]
병합정렬 할 배열 [ 4 ] [ 1 ]
병합정렬 된 배열 [ 1, 4 ]
분할 할 배열 [ 8, 7, 9 ]
좌측배열 [ 8 ] 우측배열 [ 7, 9 ]
분할 할 배열 [ 8 ]
반환한 배열 [ 8 ]
분할 할 배열 [ 7, 9 ]
좌측배열 [ 7 ] 우측배열 [ 9 ]
분할 할 배열 [ 7 ]
반환한 배열 [ 7 ]
분할 할 배열 [ 9 ]
반환한 배열 [ 9 ]
병합정렬 할 배열 [ 7 ] [ 9 ]
병합정렬 된 배열 [ 7, 9 ]
병합정렬 할 배열 [ 8 ] [ 7, 9 ]
병합정렬 된 배열 [ 7, 8, 9 ]
병합정렬 할 배열 [ 1, 4 ] [ 7, 8, 9 ]
병합정렬 된 배열 [ 1, 4, 7, 8, 9 ]
병합정렬 할 배열 [ 2, 3, 5, 6 ] [ 1, 4, 7, 8, 9 ]
병합정렬 된 배열 [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
profile
프런트엔드 개발자

0개의 댓글