🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
정렬 - 병합 정렬
📍 병합 정렬(Merge Sort)
👉🏻 다른 정렬보다는 조금 복잡함
👉🏻 분할 정복(divide and conquer)을 이용할 것
[3, 5, 2, 4, 1, 7, 8, 6]
// 한 번에 8개의 원소를 정렬하기 어려우니까 반으로 쪼개서 먼저 생각함!
[3, 5, 2, 4] [1, 7, 8, 6]
// 또 반으로 쪼개면 더 편하지 않을까?
[3, 5] [2, 4] [1, 7] [8, 6]
// 또 쪼개면?
[3] [5] [2] [4] [1] [7] [8] [6]
// 정렬이 필요 없을 정도로 단순해짐!
// 이제 순서대로 병합!
[3, 5] [2, 4] [1, 7] [6, 8]
// 각 배열의 두 개의 원소는 모두 정렬됨!
[2, 3, 4, 5] [1, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
// 정렬 끝!
👉🏻 재귀와 아주 비슷한 형태로 재귀를 이용한 정렬 알고리즘임
📍 병합 정렬의 구현
[ merge_sort.mjs ]
function MergeSort(arr, leftIndex, rightIndex) {
// 2개의 인덱스는 재귀를 활용할 때 필요한 인덱스임
// [3, 5, 2, 4, 1, 7, 8, 6]에서 3이 leftIndex, 6이 rightIndex가 됨
if(leftIndex < rightIndex) { // 기저 조건
let midIndex = parseInt((leftIndex + rightIndex) / 2); // 중간값은 3이 됨
MergeSort(arr, leftIndex, midIndex);
MergeSort(arr, midIndex + 1, rightIndex);
// arr는 중간을 기준으로 정렬이 완료되었을 것!
// [2, 3, 4, 5 / 1, 6, 7, 8]
Merge(arr, leftIndex, midIndex, rightIndex);
}
}
function Merge(arr, leftIndex, midIndex, rightIndex) {
let leftAreaIndex = leftIndex; // 왼쪽 영역 몇 번째까지 정렬되었는가?
let rightAreaIndex = midIndex + 1;
let tempArr = [];
tempArr.length = rightIndex + 1;
tempArr.fill(0, 0, rightIndex + 1);
let tempArrIndex = leftIndex;
while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
if(arr[leftAreaIndex] <= arr[rightAreaIndex]) { // 왼쪽 영역 *번째보다 오른쪽 영역 *번째가 크다면
tempArr[tempArrIndex] = arr[leftAreaIndex++]; // 왼쪽 영역을 정렬할 배열에 넣고 왼쪽 영역 다음 인덱스를 계산할 것
}else { // 오른쪽이 더 크다면
tempArr[tempArrIndex] = arr[rightAreaIndex++]; // 오른쪽 영역을 정렬할 배열에 넣고 오른쪽 영역 다음 인덱스를 계산할 것
}
tempArrIndex++;
}
if(leftAreaIndex > midIndex) {
for(let i = rightAreaIndex; i <= rightIndex; i++) {
tempArr[tempArrIndex++] = arr[i];
}
} else {
for(let i = leftAreaIndex; i <= midIndex; i++) {
tempArr[tempArrIndex++] = arr[i];
}
}
for(let i = leftIndex; i <= rightIndex; i++) {
arr[i] = tempArr[i];
}
}
let arr = [3, 5, 2, 4, 1, 7, 8, 6];
console.log("===== 정렬 전 =====");
console.log(arr);
MergeSort(arr, 0, arr.length - 1);
console.log("===== 정렬 후 =====");
console.log(arr);
👉🏻 각 영역을 거칠 때마다 정렬해야 하는 수가 적어지므로 병합 정렬의 성능은 O(nlogn)
📍 병합 정렬의 장단점
👉🏻 장점: 성능이 매우 좋음
👉🏻 단점: 이해와 구현이 어려움