병합 정렬 (Merge Sort)
: 큰 배열을 잘게 나눴다가, 정렬하면서 다시 합쳐 정렬을 완료하는 알고리즘
- 분할 정복 알고리즘(divide and conquer)
: 복잡한 문제를 한 번에 해결하려 하지 말고, 작은 문제로 쪼개서 각각 해결한 후 결과를 합쳐 전체 문제를 해결하는 방식 - 재귀로 정렬하는 알고리즘
병합 정렬의 성능
- 시간 복잡도: O(n log n)
- 병합 정렬에서 성능을 평가하는 부분
⇒ Merge() 함수 내에서 흩어진 배열을 합치는 부분
병합 정렬의 장단점
장점
- 전체적으로 성능이 좋음
단점
- 이해와 구현이 어려움
병합 정렬 알고리즘 흐름
원본: 3 5 2 4 1 7 8 6
1단계: 3 5 2 4 1 7 8 6 → 2개로 쪼갬
2단계: 3 5 2 4 1 7 8 6 → 4개로 쪼갬
3단계: 3 5 2 4 1 7 8 6 → 개별로 쪼갬- 이제 분할했던 배열들을 개별로 쪼갠 것부터 순서대로 병합함
- ex) 3과 5를 순서에 맞게 하나의 배열로 병합함 ⇒ [3, 5]
- 그 다음 2개로 묶인 배열을 순서대로 병합함
- ex) [3, 5]가 들어있는 배열과 [2, 4]가 들어있는 배열을 순서에 맞게 병합함 ⇒ [2, 3, 4, 5]
- 이전 단계와 마찬가지로 4개로 묶인 배열들을 병합함
- ex) [1, 2, 3, 4, 5, 6, 7, 8]
예시: 무작위 배열을 병합 정렬로 정렬하기
let arr = [3, 5, 2, 4, 1, 7, 8, 6];
MergeSort 함수
function MergeSort(arr, leftIndex, rightIndex){
if(leftIndex < rightIndex){ // leftIndex는 0번째 인덱스, rightIndex는 마지막 인덱스
let midIndex = parseInt((leftIndex + rightIndex) / 2);
// 배열을 분할하기 위해 중간값을 구함(정수로 변환)
MergeSort(arr, leftIndex, midIndex); // 왼쪽 절반 정렬
MergeSort(arr, midIndex + 1, rightIndex); // 오른쪽 절반 정렬
Merge(arr, leftIndex, midIndex, rightIndex); // 두 개를 병합
}
}- 배열을 왼쪽 구역(leftIndex ~ midIndex), 오른쪽 구역(midIndex+1 ~ rightIndex)으로 나눔
- 나눈 부분을 재귀적으로 다시 MergeSort에 넣음
- 더 이상 나눌 수 없을 때(= 원소가 1개일 때) 정렬을 시작함
- 나눈 배열을 Merge 함수를 이용해 병합함
Merge 함수
// [2,3,4,5, 6,7,8,9]
function Merge(arr, leftIndex, midIndex, rightIndex){
let leftAreaIndex = leftIndex; // 왼쪽 영역의 몇 번째 인덱스가 정렬됐는지 알려주는 변수
let rightAreaIndex = midIndex + 1; // 오른쪽 영역의 몇 번째 인덱스가 정렬됐는지 알려주는 변수
let tempArr = []; // 0으로 초기화 된 배열
tempArr.length = rightIndex + 1;
tempArr.fill(0);
let tempArrIndex = leftIndex; // temp 배열에서 어디까지 정렬이 됐는지 알려주는 변수
// 왼쪽, 오른쪽 영역 비교하며 작은 값을 tempArr에 넣음
while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex){
// 왼쪽 영역과 오른쪽 영역이 정렬되지 않는 동안 ⇒ 왼쪽 영역의 인덱스가 오른쪽 영역을 침범하지 않는 동안
if(arr[leftAreaIndex] <= arr[rightAreaIndex]){
// 왼쪽 영역의 데이터가 오른쪽 영역의 데이터보다 작거나 같으면
tempArr[tempArrIndex] = arr[leftAreaIndex++];
// 왼쪽 영역의 데이터를 tempArr에 넣어주고 leftAreaIndex를 1 늘려서 왼쪽 영역의 다음 인덱스로 이동함
}else{ // 왼쪽 영역의 데이터가 오른쪽 영역의 데이터보다 크면
tempArr[tempArrIndex] = arr[rightAreaIndex++];
// 오른쪽 영역의 데이터를 tempArr에 넣어주고 rightAreaIndex를 1 늘려서 오른쪽 영역의 다음 인덱스로 이동함
}
tempArrIndex++;
// tempArr에 데이터를 넣어줬으니 tempArrIndex도 1 늘림 ⇒ tempArr에서 다음 인덱스로 이동시킴
}
// 남은 원소 처리
if(leftAreaIndex > midIndex){ // 오른쪽 영역이 병합이 덜 됐다면
for(let i = rightAreaIndex; i <= rightIndex; i++){
// 오른쪽 영역의 나머지를 차례대로 tempArr에 넣어줌
tempArr[tempArrIndex++] = arr[i];
}
} else{ // 왼쪽 영역이 병합이 덜 됐다면
for(let i = leftAreaIndex; i <= midIndex; i++){
// 왼쪽 영역의 나머지를 차례대로 tempArr에 넣어줌
tempArr[tempArrIndex++] = arr[i];
}
}
// tempArr의 값들을 그대로 arr에 복사함
for(let i = leftIndex; i <= rightIndex; i++){
arr[i] = tempArr[i];
}
}
console.log("===== 정렬 전 =====");
console.log(arr); // [ 3, 5, 2, 4, 1, 7, 8, 6 ]
MergeSort(arr, 0, arr.length - 1);
console.log("===== 정렬 후 =====");
console.log(arr); // [ 1, 2, 3, 4, 5, 6, 7, 8 ]
실행 흐름
let arr = [3, 5, 2, 4, 1, 7, 8, 6];
MergeSort(arr, 0, arr.length - 1);
- 1단계: 배열을 나누기
- 전체 배열: [3, 5, 2, 4, 1, 7, 8, 6]
👉 중간 인덱스 = (0+7)/2 = 3 → 두 부분으로 나눔
- 왼쪽: [3, 5, 2, 4]
- 오른쪽: [1, 7, 8, 6]
- 왼쪽 [3, 5, 2, 4] 나누기
👉 중간 인덱스 = (0+3)/2 = 1
- 왼쪽: [3, 5]
- 오른쪽: [2, 4]
→ 다시 나누면 - [3], [5]
- [2], [4]
- 오른쪽 [1, 7, 8, 6] 나누기
👉 중간 인덱스 = (4+7)/2 = 5
- 왼쪽: [1, 7]
- 오른쪽: [8, 6]
→ 다시 나누면 - [1], [7]
- [8], [6]
- 전체 배열: [3, 5, 2, 4, 1, 7, 8, 6]
- 2단계: 병합하며 정렬하기 ⇒ 가장 작은 단위부터 병합
- [3] + [5] → 비교: 3 < 5 → [3, 5]
- [2] + [4] → 비교: 2 < 4 → [2, 4]
- [1] + [7] → 비교: 1 < 7 → [1, 7]
- [8] + [6] → 비교: 6 < 8 → [6, 8]
- 3단계: 2개짜리 배열 병합
- [3, 5] + [2, 4]
- 3 vs 2 → 2
- 3 vs 4 → 3
- 5 vs 4 → 4
- 남은 5
👉 결과: [2, 3, 4, 5]
- [1, 7] + [6, 8]
- 1 vs 6 → 1
- 7 vs 6 → 6
- 7 vs 8 → 7
- 남은 8
👉 결과: [1, 6, 7, 8]
- [3, 5] + [2, 4]
- 마지막 병합
- [2, 3, 4, 5] + [1, 6, 7, 8]
- 2 vs 1 → 1
- 2 vs 6 → 2
- 3 vs 6 → 3
- 4 vs 6 → 4
- 5 vs 6 → 5
- 남은: 6, 7, 8
👉 결과: [1, 2, 3, 4, 5, 6, 7, 8]
- [2, 3, 4, 5] + [1, 6, 7, 8]