지금까지 배운 정렬 알고리즘(버블, 선택, 삽입 정렬)
은 큰 규모에 맞지 않는 알고리즘이다.
우리가 이제부터 알아볼 빠른 알고리즘 집합은 시간 복잡도를 O(n^2)에서 O(n log n)으로 향상시킬 수 있는 알고리즘이다.
그중 합병 정렬(Merge Sort)에 대해 먼저 알아보자.
합병 정렬에 대해 간단히 얘기하자면 n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)한다.
이를 분할 정복(Divide and conquer)이라고 한다.
이번에도 글로만 봐서는 이해하기 힘들 수 있으니 작동방식을 직접 살펴보자.
이번엔 개인적으로 visualgo에서 확인하는 것 보다 위 사진이 더 이해가 잘 된다고 생각하여 사진으로 준비했다.
function merge(arr1: number[], arr2: number[]) {
let result = [];
let i = 0;
let j = 0;
while (i < arr1.length && j < arr2.length) {
if (arr2[j] > arr1[i]) {
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
while (i < arr1.length) {
result.push(arr1[i]);
i++;
}
while (j < arr2.length) {
result.push(arr2[j]);
j++;
}
return result;
}
function mergeSort(arr: number[]) {
if (arr.length <= 1) return arr;
let mid: number = Math.floor(arr.length / 2);
let left: number[] = mergeSort(arr.slice(0, mid));
let right: number[] = mergeSort(arr.slice(mid));
return merge(left, right);
}
mergeSort([16, 23, 9, 25, 5, 48]); // [5, 9, 16, 23, 25, 48]
먼저 merge 함수를 작성했다.
숫자가 담긴 2개의 배열을 순서를 정렬하여 합치는 배열이다.
그 다음, mergeSort 함수를 작성했다.
mergeSort 함수는 재귀적으로 배열을 반으로 자르고 merge하여 정렬된 배열을 반환하는 함수이다.
합병정렬의 시간복잡도 빅오는 최적의 경우, 최악의 경우, 보통 모두 시간복잡도가 O(n log n)으로 동일하다.
간단한 예시를 한번 살펴보자.
8
44
2222
11111111
이렇게 배열의 길이가 8일 시, 총 3번 분할되는것을 알 수 있다.
때문에 log n번만큼 분할되고 각 분할마다 합병할 때 n번 비교하기때문에 총 O(n log n) 이 되는것이다.