merge sort

2022/12/29 카테고리 Algorithm

merge sort

mergeSort

정렬되지 않는 배열을 각각 하나의 원소만 포함하는 n개의 부분 배열로 분할한다. n개의 부분 배열이 1개가 될 때까지 반복해서 병합할 때 정렬한다. 최종적으로 남은 부분 배열이 정렬된 배열이 된다.

두가지 역할을 하는 함수로 나누어 설명할 수 있다.

mergeSort(arr): 배열을 절반으로 나누는 함수
merge(left, right): 반으로 나뉜 두 배열을 정렬하여 새로운 배열로 병합하는 함수

merge 함수 구현

left[0]과 right[0]를 비교하여 더 작은 수를 새로운 배열에 순서대로 담는다.

만약 left[0]이 right[0]보다 작다면 새로운 배열에 left[0]을 담고 이후에 left[1]과 right[0]을 비교한다.

이렇게 비교하면서 새로운 배열을 생성하기를 left, right 배열의 요소가 하나도 남지 않을 때 까지 반복한다.

이게 가능하기 위해서는 left와 right는 정렬된 상태의 배열이여야만 합니다. left, right를 정렬된 배열로 만들어 주기 위해서 mergeSort 함수를 이용합니다.

mergeSort 함수 구현

mergeSort 함수는 인수로 주어진 배열을 요소가 1개일 때까지 절반으로 나누고 정렬하며 merge 해주는 함수이다.

즉, 요소가 1개인 서로 다른 두 배열을 정렬하면서 하나의 배열로 만들어간다.

const arr = [33,2,51,1,10,3];

// 1단계 - 나누기
[33,2,51], [1,10,3]

// 2단계 - 나누기
[33,2],[51],[1,10],[3]

// 3단계 - 나누기
[33],[2],[51],[1],[10],[3]

// 4단계 - 병합
[2,33], [1,51], [3,10]

// 5단계 - 병합
[1,2,33,51], [3, 10]

// 6단계 - 최종 병합
[1,2,3,10,33,51]

코드 구현

const merge = (left, right) => {
  const sorted = [];
  
  // left, right 비교하여 정렬된 배열에 담는다.
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      sorted.push(left.shift());
    } else {
      sorted.push(right.shift());
    }
  }

  // left 또는 right 배열 중 하나는 아직 남아있으므로 남은 배열은 정렬되어 있으므로 복사하여 뒤에 붙혀준다.
  return [...sorted, ...left, ...right];
}

const mergeSort = arr => {
  if (arr.length === 1) return arr;
  const mid = Math.ceil(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

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

const arr = [33,2,51,1,10,3];
const sorted = mergeSort(arr);
console.log(arr); // [33,2,51,1,10,3]
console.log(sorted); // [1,2,3,10,33,51]

정리

mergeSort는 O(n log n) 시간 복잡도를 가진다. 왜냐하면 절반씩 나눠서 비교하기 때문이다.
안정 정렬에 속한다.

참고자료

댓글 공유

merge sort

merge sort

merge 함수 구현

mergeSort 함수 구현

코드 구현

정리

loco9939