안녕하세요! 이번 블로그 포스트에서는 자바스크립트 코딩테스트를 준비하는 여러분을 위해 병합 정렬(Merge Sort) 알고리즘에 대해 다뤄보겠습니다. 병합 정렬은 매우 널리 사용되는 정렬 알고리즘 중 하나로, 시간 복잡도가 O(n log n)이며 뛰어난 성능을 보입니다. 본 포스트에서는 병합 정렬의 개념, 동작 방식, 자바스크립트로의 구현, 그리고 실제 코딩 테스트에서의 활용 사례를 극적으로 설명하겠습니다.
병합 정렬이란?
병합 정렬은 분할 정복(divide and conquer) 방법을 사용하는 알고리즘입니다. 이 알고리즘의 기본 아이디어는 배열을 두 개의 하위 배열로 재귀적으로 나누고, 각각의 하위 배열을 정렬한 후, 이 두 하위 배열을 합쳐 하나의 정렬된 배열을 만드는 것입니다. 병합 정렬은 다음과 같은 단계를 거칠습니다:
- 배열을 중간 기준에 따라 두 개의 하위 배열로 나눈다.
- 각 하위 배열을 재귀적으로 정렬한다.
- 정렬된 두 하위 배열을 병합하여 최종적으로 하나의 정렬된 배열을 생성한다.
병합 정렬의 동작 과정
병합 정렬의 동작 과정을 예를 들어 살펴보겠습니다. 정렬할 배열이 [38, 27, 43, 3, 9, 82, 10]라고 가정해보겠습니다.
1단계: 배열 나누기
우선 배열을 중간을 기준으로 나누어 보겠습니다. 이 배열은 중앙에서 나누면 다음과 같이 두 개의 하위 배열로 나눌 수 있습니다:
- [38, 27, 43]
- [3, 9, 82, 10]
2단계: 재귀적 정렬
이제 각각의 하위 배열에 대해 동일한 과정을 반복합니다. 계속해서 나누면:
- [38, 27] -> [38]와 [27]
- [3, 9, 82, 10] -> [3, 9]와 [82, 10] -> [3]와 [9], [82]와 [10]
3단계: 정렬 후 병합하기
이제 각 하위 배열이 하나의 원소로 나뉘어졌습니다. 이 원소들을 정렬하면서 다시 합쳐 보겠습니다:
- [38]와 [27]을 합쳐 [27, 38]
- [3]와 [9]를 합쳐 [3, 9]
- [82]와 [10]을 합쳐 [10, 82]
이제 정렬된 하위 배열들이 되었으니, 다시 한 번 병합해 보겠습니다:
- [27, 38]와 [3, 9] -> [3, 9, 27, 38]
- [3, 9, 27, 38]와 [10, 82] -> [3, 9, 10, 27, 38, 82]
최종적으로 정렬된 배열은 [3, 9, 10, 27, 38, 82]가 됩니다.
병합 정렬의 시간 복잡도 분석
병합 정렬의 시간 복잡도는 O(n log n)입니다. 이는 두 가지 요인이 결합된 결과입니다:
- 배열을 나누는 과정에서 배열의 크기가 절반씩 줄어드므로 log n에 해당하는 단계가 발생합니다.
- 각 단계에서 두 개의 하위 배열을 합치는 데 O(n)의 시간이 소요됩니다.
결과적으로, 병합 정렬은 안정적인 정렬 방법으로 널리 사용됩니다. 하지만 메모리 사용량이 상대적으로 많다는 단점이 있습니다.
자바스크립트로 병합 정렬 구현하기
이제 자바스크립트에서 병합 정렬을 구현해 보겠습니다. 병합 정렬은 기본적으로 재귀 함수를 사용합니다. 아래는 자바스크립트 코드입니다:
function mergeSort(arr) {
if (arr.length <= 1) {
return arr; // 기본 경우: 요소가 하나일 때, 그대로 반환
}
const mid = Math.floor(arr.length / 2); // 배열의 중간 인덱스
const left = mergeSort(arr.slice(0, mid)); // 왼쪽 부분 재귀 정렬
const right = mergeSort(arr.slice(mid)); // 오른쪽 부분 재귀 정렬
return merge(left, right); // 정렬된 두 부분을 병합
}
function merge(left, right) {
const sortedArray = [];
let leftIndex = 0; // 왼쪽 배열 인덱스
let rightIndex = 0; // 오른쪽 배열 인덱스
// 양쪽 배열 중 하나가 비어있지 않은 동안 반복
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
sortedArray.push(left[leftIndex]); // 왼쪽에서 더 작은 원소 추가
leftIndex++;
} else {
sortedArray.push(right[rightIndex]); // 오른쪽에서 더 작은 원소 추가
rightIndex++;
}
}
// 남아 있는 원소들 추가
return sortedArray.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
// 테스트
const array = [38, 27, 43, 3, 9, 82, 10];
const sortedArray = mergeSort(array);
console.log(sortedArray); // 결과: [3, 9, 10, 27, 38, 43, 82]
병합 정렬의 활용과 주의사항
병합 정렬이 가장 많이 쓰이는 곳은 대량의 데이터를 정렬해야 하는 경우입니다. 특히 외부 정렬(예: 파일 정렬)에서 매우 유용합니다. 병합 정렬은 안정적인 정렬 알고리즘이므로, 원래의 순서를 유지해야 하는 경우에 적합합니다. 다만, 메모리를 상당히 소모하기 때문에 메모리 제약이 있는 환경에서는 다른 알고리즘을 고려해야 할 수도 있습니다.
마치며
이번 포스트에서는 병합 정렬에 대해 상세히 알아보았습니다. 알고리즘의 기본 개념부터 구현까지, 코딩 테스트에서도 유용하게 사용할 수 있는 내용을 다루었어요. 병합 정렬을 잘 이해하고 구현할 수 있다면, 기초가 튼튼해진 만큼 다른 알고리즘도 쉽게 습득할 수 있을 것입니다. 코딩 테스트 준비에 도움이 되길 바라며, 다음 포스트에서도 더 유익한 정보를 가지고 돌아오겠습니다. 감사합니다!