오늘 다룰 정렬 알고리즘은 병합정렬입니다.
병합정렬은 합병정렬이라고도 부르는데 분할정복 알고리즘으로 안정적인 정렬이라는 특징을 가지고 있습니다.
- 분할정복 알고리즘(Divide-and-conquer algorithm)이란?
분할 정복 알고리즘은 복잡한 기존 문제를 단순화하기 위해 재귀적으로 접근해 2개 이상의 하위 문제로 분할합니다.
이후, 하위 문제에서 해결 한 정답을 병합 과정에서 조합하여 최종 정답을 얻는 풀이방법입니다.
정렬 알고리즘에서는 퀵 정렬과 병합 정렬이 분할 정복 알고리즘에 해당합니다.
위 애니메이션을 보면 요소가 한개가 될때까지 배열을 분할하고 병합하는 과정에서 요소들이 오름차순으로 정렬되는 모습을 볼 수 있습니다.
이러한 과정을 통해 최선, 평균, 최악의 시간복잡도가 O(n log n)
으로 일관된 시간 복잡도를 가지고 있으며 이는 정렬 알고리즘 중 성능이 좋은 편에 속합니다.
다만, 병합 과정에서 임시적으로 배열을 저장해야 하기 때문에 추가적인 메모리를 사용하므로 O(n)
의 공간 복잡도를 가진다는 단점도 있습니다.
아래의 구현 로직은 오름차순 정렬을 기준으로 작성하였습니다.
지금까지 다뤘던 정렬에 비해 구현이 복잡하고 여러개의 함수를 사용하기 때문에 한 개의 함수씩 천천히 살펴보도록 하겠습니다.
먼저, 병합 정렬에서는 3개의 함수를 사용합니다.
메인 함수인 mergeSort
함수,
분할 과정을 담당하는 divide
함수,
병합 및 정렬이 이루어지는 conquer
함수로 나누어집니다.
메인함수인 mergeSort
는 분할을 위해 divide
함수를 호출하며
divide
함수가 종료된다면 arr
을 그대로 반환하는 단순한 로직을 갖고 있습니다.
아래에서 다룰 divide
함수는 분할 대상 범위가 주어져야 하기 때문에 초기에는 0 ~ arr.length-1
까지로 설정합니다.
divide
함수는 매개변수로 받은 배열의 범위를 2개로 분할합니다.
이 때, left
는 시작점, right
는 끝점을 의미하며
만약, left
가 right
보다 크거나 같다면 요소의 수가 한 개 미만이라 정렬 할 필요가 없으므로 2번라인처럼 함수를 바로 종료해줍니다.
4번 라인에서는 배열을 분할할 기준이 될 인덱스인 m
변수를 선언해주고
overflow 방지를 위해서 left + (right - left) / 2
와 같이 중간 인덱스를 구해줍니다.
이후, 정렬 대상 요소의 개수가 한 개가 될 때까지 divide
함수는 재귀적으로 호출되며 요소가 모두 한 개로 분할 되었다면 9번 라인에서 conquer
함수가 호출됩니다.
overflow란?
overflow는 컴퓨터가 표현할 수 있는 최대 수보다 더 큰 숫자를 다룰 경우 해당 숫자가 제일 작은 수 혹은 음수로 변경되는것을 말합니다.예를 들어, 컴퓨터가 표현할 수 있는 최대수가 120이고 left가 50, right가 100이라고 가정해보겠습니다.
중간값을 구하기 위해
(left + right) / 2
와 같이 간단한 수식을 사용할 수도 있지만이는 계산 과정에서
left+right
로 인해 150이라는 숫자가 등장해 표현가능한 최대 수를 넘기기 때문에 결과값이 의도와 다르게 나올 수 있습니다.반면, 위 코드에서 작성했던 수식을 사용한다면
50 + (100 - 50) / 2
이므로 계산 과정에서 120을 넘는 숫자는 등장하지 않아 안정적으로 계산 과정을 진행할 수 있습니다.
병합정렬 로직 중 가장 중요하면서 복잡한 로직입니다.
먼저, 정렬한 요소를 임시로 담는 tempArr
배열을 정의해줍니다.
이후, 3개의 변수를 선언하는데 i
는 왼쪽 파티션의 인덱스, j
는 오른쪽 파티션의 인덱스, k
는 tempArr
의 인덱스를 가르킵니다.
- 파티션이란?
분할 과정에서 쪼개진 요소들을 각각 파티션이라고 합니다.
병합정렬에서는divide
함수가 호출될때마다 인풋으로 받았던 한 개의 범위를 두 개로 나누므로 함수가 호출될 때마다 2개의 파티션이 생깁니다.
이후에는 4개의 while문을 사용해 정렬 및 병합을 진행합니다.
tempArr
에 삽입합니다. while(left <= m && j <= right) {
if(arr[i] <= arr[j]) {
tempArr[k] = arr[i];
i++;
} else {
tempArr[k] = arr[j];
j++;
}
k++;
}
tempArr
에 삽입되도록 합니다.tempArr
에 전부 넣어주면 됩니다. while(left <= m) {
tempArr[k] = arr[i];
i++;
k++;
}
tempArr
에 삽입되도록 합니다. while(j <= right) {
tempArr[k] = arr[j];
j++;
k++;
}
tempArr
에 저장된 요소들을 기존 arr에 반영합니다.k
는 요소가 없는 tempArr.length
와 같은 인덱스를 가르키고 있을것이기 때문에 먼저 1을 줄여준뒤 요소들을 기존 arr
에 반영해줍니다. k--;
while(k >= 0) {
arr[left + k] = tempArr[k];
k--;
}
병합정렬에 최종 코드는 아래와 같습니다.
function conquer(arr, left, mid, right) {
const tempArr = new Array();
let i = left;
let j = mid+1;
let k = 0;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
tempArr[k] = arr[i];
i++;
} else {
tempArr[k] = arr[j];
j++;
}
k++;
}
while(i <= mid) {
tempArr[k] = arr[i];
i++;
k++;
}
while(j <= right) {
tempArr[k] = arr[j];
j++;
k++;
}
k--;
while(k >= 0) {
arr[left + k] = tempArr[k];
k--;
}
}
function divide(arr, left, right) {
if (left >= right) return;
const m = Math.floor(left + (right - left) / 2);
divide(arr, left, m);
divide(arr, m+1, right);
conquer(arr, left, m, right);
}
function mergeSort(arr) {
const n = arr.length-1;
divide(arr, 0, n);
return arr;
}
console.log(mergeSort([8, 5, 4, 7, 3, 1, 2, 6]));
비교적 로직이 복잡하고 재귀적으로 함수가 호출되기 때문에 코드만 읽고 바로 이해하기는 어려울 수 있습니다.
만약, 로직 흐름이 이해되지 않는다면 과정을 시각적으로 확인할 수 있는 JS Visualizer를 이용해 보는것을 추천드립니다.
여러 비쥬얼라이저를 찾아보다가 Python Tutor 라는 사이트를 발견했는데 다른 비쥬얼라이저의 경우 JS 버전에 제약이 있거나 단순히 함수명만 보여주어 이해하기 어려운데 이 사이트는 인풋이 어떻게 변화하는지, 수행되고 있는 함수들의 인자는 무엇인지를 보여주어 훨씬 이해하기 좋지 않을까 생각합니다.
JS뿐만 아니라 Python코드도 가능하며 코드 붙여넣기도 가능하기 때문에 위 최종코드를 이용해서 한번 테스트 해보시는걸 추천드립니다.