정렬 - 병합정렬 (Merge Sort)
오늘 다룰 정렬 알고리즘은 병합정렬입니다.
병합정렬은 합병정렬이라고도 부르는데 분할정복 알고리즘으로 안정적인 정렬이라는 특징을 가지고 있습니다.
- 분할정복 알고리즘(Divide-and-conquer algorithm)이란?
분할 정복 알고리즘은 복잡한 기존 문제를 단순화하기 위해 재귀적으로 접근해 2개 이상의 하위 문제로 분할합니다.
이후, 하위 문제에서 해결 한 정답을 병합 과정에서 조합하여 최종 정답을 얻는 풀이방법입니다.
정렬 알고리즘에서는 퀵 정렬과 병합 정렬이 분할 정복 알고리즘에 해당합니다.
위 애니메이션을 보면 요소가 한개가 될때까지 배열을 분할하고 병합하는 과정에서 요소들이 오름차순으로 정렬되는 모습을 볼 수 있습니다.
이러한 과정을 통해 최선, 평균, 최악의 시간복잡도가 O(n log n)으로 일관된 시간 복잡도를 가지고 있으며 이는 정렬 알고리즘 중 성능이 좋은 편에 속합니다.
다만, 병합 과정에서 임시적으로 배열을 저장해야 하기 때문에 추가적인 메모리를 사용하므로 O(n)의 공간 복잡도를 가진다는 단점도 있습니다.
구현
아래의 구현 로직은 오름차순 정렬을 기준으로 작성하였습니다.
지금까지 다뤘던 정렬에 비해 구현이 복잡하고 여러개의 함수를 사용하기 때문에 한 개의 함수씩 천천히 살펴보도록 하겠습니다.
먼저, 병합 정렬에서는 3개의 함수를 사용합니다.
메인 함수인 mergeSort 함수,
분할 과정을 담당하는 divide 함수,
병합 및 정렬이 이루어지는 conquer 함수로 나누어집니다.
mergeSort 함수
메인함수인 mergeSort는 분할을 위해 divide 함수를 호출하며
divide 함수가 종료된다면 arr을 그대로 반환하는 단순한 로직을 갖고 있습니다.
아래에서 다룰 divide 함수는 분할 대상 범위가 주어져야 하기 때문에 초기에는 0 ~ arr.length-1 까지로 설정합니다.
divide 함수
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을 넘는 숫자는 등장하지 않아 안정적으로 계산 과정을 진행할 수 있습니다.
conquer 함수
병합정렬 로직 중 가장 중요하면서 복잡한 로직입니다.
먼저, 정렬한 요소를 임시로 담는 tempArr 배열을 정의해줍니다.
이후, 3개의 변수를 선언하는데 i는 왼쪽 파티션의 인덱스, j는 오른쪽 파티션의 인덱스, k는 tempArr의 인덱스를 가르킵니다.
- 파티션이란?
분할 과정에서 쪼개진 요소들을 각각 파티션이라고 합니다.
병합정렬에서는divide함수가 호출될때마다 인풋으로 받았던 한 개의 범위를 두 개로 나누므로 함수가 호출될 때마다 2개의 파티션이 생깁니다.
이후에는 4개의 while문을 사용해 정렬 및 병합을 진행합니다.
- 첫 번째 while문은 두 파티션 모두 정렬 해야 할 요소가 남아있을 때
각 파티션의 앞에 위치한 요소의 값을 비교하고 더 작은 값을 먼저tempArr에 삽입합니다.
앞 쪽 요소부터 접근하는 이유는 병합 과정에서 각 파티션은 이미 정렬이 이루어진 상태이기 때문에 맨 앞의 요소가 해당 파티션에서 가장 작은 수이기 때문입니다.
이 while문은 두 파티션 중 하나의 파티션이라도 더이상 정렬 할 요소가 없을 때 종료됩니다.
while(left <= m && j <= right) {
if(arr[i] <= arr[j]) {
tempArr[k] = arr[i];
i++;
} else {
tempArr[k] = arr[j];
j++;
}
k++;
}- 두 번째 while은 만약 왼쪽 파티션에 정렬이 필요한 요소가 있다면 모두
tempArr에 삽입되도록 합니다.
이 while문을 만났다는건 1번 while문에서 말했다시피 이미 한 쪽 파티션의 정렬이 완료된 상태이기 때문에 추가적인 정렬이 필요 없으므로tempArr에 전부 넣어주면 됩니다.
while(left <= m) {
tempArr[k] = arr[i];
i++;
k++;
}- 두 번째 while문과 마찬가지로 오른쪽 파티션에 남은 요소들이 있다면 모두
tempArr에 삽입되도록 합니다.
while(j <= right) {
tempArr[k] = arr[j];
j++;
k++;
}- 네 번째 while문에서는
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코드도 가능하며 코드 붙여넣기도 가능하기 때문에 위 최종코드를 이용해서 한번 테스트 해보시는걸 추천드립니다.
