[JS]merge sort(합병/병합 정렬)

Kyle·2020년 12월 22일

Merge sort 알고리즘 합병 정렬

algorithm & Data structure

목록 보기

6/8

합병정렬(merge sort)

자바스크립트의 기본 정렬알고리즘인 Timsort를 알기 위해서 합병정렬을 먼저 공부했습니다.

합병정렬이란?

(출처: 위키피디아_합병정렬)

위의 그림과 같은 방식으로 작동해 배열을 정렬시켜주는 알고리즘입니다.
합병 정렬은 비교 기반 정렬 알고리즘으로 시간복잡도는 O(NlogN)입니다.

합병정렬 javascript로 구현하기

위와 같은 방식으로 작동하게 구현하면 됩니다.

2가지 함수를 이용해서 구현할 수 있습니다.

mergeSort(arr): 반으로 나누어 주는 함수
merge(left,right): 반으로 나누어준 함수를 갖고 정렬해 새로운 배열로 만들어주는 함수
(이 과정에서 새로운 배열로 만들어 주기 때문에 메모리가 조금 필요합니다.)

각각의 함수가 어떻게 구성돼 있는지 자세히 알아봅시다.

merge(left,right)

인자로 받아온 left와 right를 합쳐주는 함수입니다.
당연히 left.concat(right) 이런식으로 그냥 붙여주는 것이 아닌 정렬을 해주면서 붙입니다.

ex) left[1,4] right[2,3]

left[0] vs right[0] 이 둘을 비교해 작은 값을 새로운 배열에 push 해줍니다.
left,right에 요소가 하나도 남지 않을 때까지 반복해 새로운 배열에 push해줍니다.

1. arr=[1] / left=[4] / right=[2,3]
2. arr=[1,2] / left=[4] / right=[3]
3. arr=[1,2,3] / left=[4] / right = []
4. right이 비었기 때문에 left에 남은 모든것을 arr에 추가해줍니다.
=> return arr=[1,2,3,4]

여기서 의문이 생깁니다. 예시의 left,right는 정렬이 돼있기 때문에 잘 정렬이 된 것이다.

맞습니다! 그렇기 때문에 mergeSort()를 이용해 요소가 1개만 있을 때 까지 나누어 주어서 merge를 해주는 식으로 해야됩니다. [1],[7] 은 무조건 [1,7]로 정렬 될테니까 말이죠!

mergeSort(arr)

mergeSort는 주어진 arr을 대략 left,right로 나누어서 merge해주는 함수입니다.
하지만 위에 말했듯이 요소가 하나일 때까지 나누고 -> 정렬 -> 정렬된 2개로 다시 정렬 -> ... 을 반복하기 위해서 재귀로 구현돼야 합니다.

즉, 재귀 종료조건(arr의 길이가 1)까지 재귀를 통해가서 요소가 1개인 2개의 배열끼리 서로 정렬하면서 상위(재귀의 상위)로 올라갑니다.

그럼 자연스레 merge함수를 보면서 생긴 의문이 해결될 것입니다!

이용되는 2가지 함수를 봤으니 코드를 보고 이해해봅시다!

function merge(left, right) {
  const sortedArr = [];
  while (left.length && right.length) {
    //left[0]이 더작을 경우 같을때는 누가 먼저 들어가도 상관X
    if (left[0] <= right[0]) {
      sortedArr.push(left.shift());
    } else {
      sortedArr.push(right.shift());
    }
  }
  //left,right 둘 중 하나는 요소가 남아있기 때문에 sortedArr 뒤에 붙여서 출력
  //비어있으면 spread Syntax에도 아무것도 없기 때문에 그냥 다 붙여준다.
  return [...sortedArr, ...left, ...right];
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  const boundary = Math.ceil(arr.length / 2);
  //slice로 해주기 때문에 원본 arr은 손상 없다.
  const left = arr.slice(0, boundary);
  const right = arr.slice(boundary);
    //요소가 1개 일 때까지 재귀를 실행해 요소가 1개일 때 두 left,right부터
  	//차근차근 merge(정렬해서 합치기)해주면 된다.
  return merge(mergeSort(left), mergeSort(right));
}

const arr = [7, 4, 3, 2, 1, 6, 5];
const sortedArray = mergeSort(arr);
console.log(arr); //[7, 4, 3, 2, 1, 6, 5]
console.log(sortedArray); //[1, 2, 3, 4,5, 6, 7]