병합정렬

유키미아우·2023년 9월 24일

본 포스팅은 Colt Steele의 JavaScript 알고리즘 & 자료구조 마스터클래스를 수강하며 정리한 노트입니다.
https://www.udemy.com/course/best-javascript-data-structures/

85. 기가 막히게 빠른 정렬 소개

버블, 선택, 삽입 정렬은 성능이 좋지 않으며 큰 규모에는 어울리지 않음.

예를 들어 버블정렬을 10만개의 숫자로 하려고하니 20초 정도 걸리는 모양새. 그러나 합병정렬을 이용하니 0.5초가 걸림.

빅오는 n log n으로써 n제곱보다 빠르다.
효율적이지만 복잡해진다.
코드가 더 길어진다.

86. 합병정렬 - 소개

이 알고리즘은 1948년 폰 노이만에 의해 개발되었다. EDVAC이라는 컴퓨터의 23페이지짜리 코드였다고 한다.

분할, 정렬, 합병
이 세 요소가 동시에 일어난다.
배열을 더 작은 배열로 나눔. 0이나 1개 배열이 되면 종료.

[8, 3, 5, 4, 7, 6, 1, 2]

[8, 3, 5, 4] [7, 6, 1, 2]

[8, 3] [5, 4] [7, 6] [1, 2]

[8] [3] [5] [4] [7] [6] [1] [2]
// 요소가 1개가 될때까지 쪼개기

[3, 8] [4, 5] [6, 7] [1, 2]

[3, 4, 5, 8]   [1, 2, 6, 7]

[1, 2, 3, 4, 5, 6, 7, 8]

87. 배열합병

정렬된 두 배열 합병을 담당할 함수를 먼저 구현한다.
정렬된 두 배열이 주어지면 이 헬퍼 함수는 마찬가지로 정렬된 새 배열을 만든다.
입력 배열 두 개에 있는 모든 요소를 포함하는 것이 중요.
O(n + m)시간과 O(n + m)공간으로 실행됌.
n이란? 첫 번째 배열의 크기
m이란? 두 번째 배열의 크기

100000개 요소의 배열과 100개 요소의 배열을 합병할 경우가 있다면 O(n + m)시간과 공간이 소요됌.
어쨌든 각 배열의 요소들을 한번씩 순회하기 때문.

슈도 코드

빈 result 배열을 만들고 각 입력 배열에서 가장 작은 값부터 스타트.
i와 j가 있으며 둘 다 0부터 시작한다.
루프에는 while을 이용한다.
각 배열의 첫번째 요소들을 비교
첫번째 요소가 작은 경우: 결과 배열에 넣고 다음 항목으로.
첫번째 요소가 클 경우: 두번째 배열의 값을 result배열에 넣고 두번째 배열의 다음 요소로 넘어간다.
배열 하나를 완료한 다음에는 다른 배열의 남은 값을 모두 넣는다.

 v			 v
[1, 10, 50] [2, 14, 99, 100]

[1] // 배열 1이 더 작으므로 담기

 	v		 v
[1, 10, 50] [2, 14, 99, 100]

[1, 2] // 배열 2가 더 작으므로 담기

 	 v		 	 v
[1, 10, 50] [2, 14, 99, 100]

[1, 2, 10] // 배열 1이 더 작으므로 담기

 	 	v		 v
[1, 10, 50] [2, 14, 99, 100]

[1, 2, 10, 14] // 배열 2가 더 작으므로 담기

 	 	v		 	v
[1, 10, 50] [2, 14, 99, 100]

[1, 2, 10, 14, 50] // 배열 1이 더 작으므로 담기

 	 			 		v
[1, 10, 50] [2, 14, 99, 100]

[1, 2, 10, 14, 50, 99, 100] // 배열 1이 끝났으므로 나머지 값 담기

88. 배열합병 - 구현

function merge(arr1, arr2) {
	let results = [];
    let i = 0;
    let j = 0;
 
    while (i < arr1.length && j < arr2.length) {
		if (arr2[j] > arr1[i]) {
        	results.push(arr1[i]);
          	i++;
        } else {
        	results.push(arr2[j]);
          	j++;
        }
    }
  	// 각 배열의 i, j 요소를 비교하고, 작은 값을 results에 담고 포인터를 이동해주는 로직
  
  	while (i < arr1.length) {
    	results.push(arr1[i]);
      	i++;
    }
    // 비교가 끝났을 시 아직 남은 값이 있다면 더해주는 로직
  
    while (j < arr2.length) {
      results.push(arr2[j]);
      j++;
    }
    // 비교가 끝났을 시 아직 남은 값이 있다면 더해주는 로직
  
  	return results;
}

merge([1, 10, 50], [2, 14, 99, 100])

89. 합병 정렬 작성하기 1부

재귀를 이용하여 배열을 반으로 계속해서 나눈다.
base case: 요소의 개수가 1이나 0일 때. 이 때에 재귀가 종료. <= 이번에 작성해 볼 로직
(위에서 먼저 다루었던) 배열합병 로직을 이용해 원래의 길이로 되돌린다.
소트된 배열을 반환한다.

90. 합병 정렬 작성하기 2부

배열을 반으로 나누기 위해서는 slice메서드를 사용한다.
어떻게 가운데를 찾을 수 있을까?
arr.length를 2로 나누고 Math.floor를 적용해준다.

function mergeSort(arr) {
	if(arr.length <= 1) return arr;
  	let mid = Math.floor(arr.length / 2);
	let left = mergeSort(arr.slice(0, mid)); // 재귀
  	let right = mergeSort(arr.slice(mid)); // 재귀
  
  	return merge(left, right); // 합병함수
}

mergeSort([10, 24, 76, 73])