JavaScript로 병합정렬(merge sort) 알고리즘 구현하기

🐶·2021년 7월 12일

알고리즘

목록 보기

13/21

병합 정렬은 표준 라이브러리에서 정렬을 구현할 때 퀵 정렬이나 힙 정렬의 대안으로 사용하는 최적화된 정렬 알고리즘이다. 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체 정렬을 하는 방법이다.

병합 정렬은 다음 세가지 과정을 통해 이루어진다.

분할(Divide): 배열을 같은 크기의 2개의 배열로 분할한다.
정복(Conquer): 분할된 배열을 정렬.
결합(Combine): 정렬된 부분 배열을 다시 합침.

수도코드

병합정렬은 아래와 같이 크게 두 파트로 나누면 좋을 것 같다.

분할된 배열을 정렬하여 합쳐주는 함수 --> function merge(left, right) : 이미 소팅된 배열 left, right 받아서 하나로 합치는 순수한 함수
배열을 2개로 분할하는 함수 --> function mergeSort(arr) : 배열을 반으로 쪼개서 merge 함수에게 left, right 인자를 넘겨주는 함수
이 때, merge함수는 순수한 함수이고, mergeSort는 재귀로 함수를 콜한다는 것을 인지해야 한다.

1. merge function
results array 선언
while left, right 모두 element 남아 있을 때까지
    left[0] <= right[0] left의 맨 앞에 것 빼서 results 에 푸쉬
    left[0] > right[0] right의 맨 앞에 것 빼서 results 에 푸쉬

return [...results, ...left, ...right] 남은 것 다 배열에 넣어주기


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

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

1. result=[1] / left=[4] / right=[2,3]
2. result=[1,2] / left=[4] / right=[3]
3. result=[1,2,3] / left=[4] / right = []
4. right이 비었기 때문에 left에 남은 모든것(이미 정렬 되어 있음)을 arr에 추가.
=> result=[1,2,3,4]

2. mergeSort function
요소가 하나일 때까지 나누고 -> 정렬 -> 정렬된 2개로 다시 정렬 -> ... 을 반복하기 위해서 재귀로 구현돼야 한다.

이 함수의 재귀 탈출 조건은 legnth 가 1일 때, 더 이상 쪼갤 수 없게 된다. => 정렬된 배열인 셈이다.
length >=2 이면 계속해서 반으로 쪼갠다

return merge( mergeSort(left), mergeSort(right) );
// legnth 1이 될 때 까지 쪼개다가 length === 1인 배열을 만나면
// 그제서야 merge함수가 실행된다. legnth 가 1일때 가장 아랫단계에서 sorted 된 것이므로.. 쭉쭉 스택콜을 타고 올라온다.

코드로 작성해보면

const merge = function (left, right) { // 정렬된 왼쪽과 오른쪽 배열을 받아서 하나로 합치는 순수한 함수
	const result = [];
	while (left.length !== 0 && right.length !== 0) {
		left[0] <= right[0] ? result.push(left.shift()) : result.push(right.shift());	
	}

	return [...result, ...left, ...right]; 
  // left,right 둘 중 하나는 요소가 남아있기 때문에 result 뒤에 붙여서 출력
}

const mergeSort = function (array) {
	// ending condition: length === 1 인 배열이 들어올 때, 정렬이 끝난 것. 
	if (array.length === 1) return array; //그 배열 그대로 리턴...! 정렬할 필요가 없으므로

	// 2로 나누고 '내림을' 해야
	// length 가 2일 때도 안전하게 배열을 slice 할 수 있다.
	const middleIndex = Math.floor(array.length / 2); 
	const left = array.slice(0, middleIndex);
	const right = array.slice(middleIndex);

	// 재귀로 계속해서 반으로 나누면서 length 가 1이 될때까지 쪼개고, 
	// 거꾸로 올라오면서 순수한 함수인 merge에 인자로 넣어서 다시 병합되어서 최종값을 리턴한다.
	return merge(mergeSort(left), mergeSort(right));
}