병합 정렬은 1945년 John von Neumann이 주로 대규모 데이터 세트 정렬의 효율성을 향상시키기 위해 도입했습니다. Von Neumann의 알고리즘은 분할 정복 방법을 사용하여 일관되고 예측 가능한 정렬 프로세스를 제공하는 것을 목표로 했습니다. 이 전략을 사용하면 병합 정렬이 작은 데이터세트와 큰 데이터세트를 모두 효과적으로 처리할 수 있어 모든 경우에 O(n log n)의 시간 복잡도로 안정적인 정렬을 보장할 수 있습니다.
병합 정렬은 배열을 더 작은 하위 배열로 분할하고 재귀적으로 정렬한 다음 정렬된 배열을 다시 병합하는 분할 정복 접근 방식을 사용합니다. 이 접근 방식은 문제를 관리 가능한 덩어리로 나누어 각 덩어리를 개별적으로 정렬하고 효율적으로 결합합니다. 결과적으로 알고리즘은 정렬 작업량을 나누어 대규모 데이터 세트에서도 잘 수행됩니다.
재귀는 동일한 문제의 더 작은 버전을 해결하기 위해 함수가 자신을 호출하는 프로세스입니다. 문제가 직접 해결할 수 있을 만큼 단순한 지점, 즉 기본 사례라고 하는 지점에 도달할 때까지 계속해서 문제를 세분화합니다.
다음은 배열이 재귀적으로 분할되고 병합되는 방식을 보여주는 JavaScript의 병합 정렬 구현입니다.
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) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) result.push(left.shift());
else result.push(right.shift());
}
return result.concat(left, right);
}
병합 정렬의 작동 방식을 더 잘 이해하기 위해 배열 [38, 27, 43, 3, 9, 82, 10]을 사용하여 프로세스를 살펴보겠습니다.
1단계: 재귀적 분할(mergeSort 기능)
배열은 각 하위 배열에 하나의 요소만 포함될 때까지 더 작은 하위 배열로 재귀적으로 분할됩니다. 이는 mergeSort 함수의 다음 행을 통해 발생합니다.
function mergeSort(arr) {
if (arr.length <= 1) return arr;
이로 인해 재귀가 중지됩니다.
재귀적 분할이 전개되는 방식은 다음과 같습니다.
전반전:
후반전:
2단계: 정렬된 하위 배열 병합(병합 기능)
이제 병합 기능을 사용하여 하위 배열을 정렬된 순서로 다시 병합하기 시작합니다.
function merge(left, right) {
let result = [];
while (left.length && right.length) {
if (left[0] < right[0]) result.push(left.shift());
else result.push(right.shift());
}
return result.concat(left, right);
}
병합 과정은 다음과 같습니다.
첫 번째 병합(기본 사례에서):
이 시점에서 배열의 왼쪽 절반이 완전히 병합되었습니다: [27, 38, 43].
두 번째 병합(기본 사례에서):
이제 오른쪽 절반이 완전히 병합되었습니다: [3, 9, 10, 82].
3단계: 최종 병합
마지막으로 두 개의 반쪽 [27, 38, 43]과 [3, 9, 10, 82]가 병합 기능을 사용하여 병합됩니다.
27(왼쪽[0])과 3(오른쪽[0])을 비교합니다. 3 < 27, 결과에 3을 더합니다.
27과 9를 비교합니다. 결과에 9를 더합니다.
27과 10을 비교합니다. 결과에 10을 더합니다.
27과 82를 비교합니다. 결과에 27을 추가합니다.
38과 82를 비교합니다. 결과에 38을 추가합니다.
43과 82를 비교합니다. 결과에 43을 추가합니다.
오른쪽 배열의 나머지 요소 82를 추가합니다.
완전히 병합되고 정렬된 배열은 다음과 같습니다.
[3, 9, 10, 27, 38, 43, 82].
시간 복잡도: 최고, 평균, 최악의 경우: O(n log n)
좀 더 자세히 살펴보겠습니다:
나누기(O(log n)): 배열을 두 부분으로 나눌 때마다 문제의 크기가 줄어듭니다. 각 단계에서 배열이 반으로 나누어지기 때문에 이를 수행할 수 있는 횟수는 log n에 비례합니다. 예를 들어 8개의 요소가 있는 경우 3번 반으로 나눌 수 있습니다(log2(8) = 3이므로).
병합(O(n)): 배열을 나눈 후 알고리즘은 더 작은 배열을 순서대로 다시 병합합니다. 크기가 n인 두 개의 정렬된 배열을 병합하려면 각 요소를 한 번 비교하고 결합해야 하기 때문에 O(n) 시간이 걸립니다.
전체 복잡도(O(n log n)): 나누기는 O(log n) 단계가 필요하고 각 단계에서 n 요소를 병합하므로 총 시간 복잡도는 이 두 가지를 곱한 것입니다: O(n log n).
공간 복잡도: O(n)
병합 정렬은 병합 단계에서 요소를 저장하기 위한 임시 배열이 필요하기 때문에 배열 크기에 비례하는 추가 공간이 필요합니다.
다른 정렬 알고리즘과 비교:
QuickSort: QuickSort의 평균 시간 복잡도는 O(n log n)이지만 최악의 경우는 O(n^2)일 수 있습니다. 병합 정렬은 이러한 최악의 시나리오를 방지하지만 일반적으로 공간이 문제가 되는 경우 메모리 내 정렬에서는 QuickSort가 더 빠릅니다.
버블 정렬: 평균 및 최악의 시나리오에서 시간 복잡도가 O(n^2)이므로 병합 정렬보다 훨씬 덜 효율적입니다.
실제 사용법
병합 정렬은 메모리에 맞지 않는 데이터를 효율적으로 처리하므로 대용량 데이터 세트를 디스크에서 정렬해야 하는 외부 정렬에 널리 사용됩니다. 또한 멀티 코어 처리를 활용하여 하위 배열을 독립적으로 정렬할 수 있는 병렬 컴퓨팅 환경에서도 일반적으로 구현됩니다.
게다가 Python(Timsort), Java, C(std::stable_sort)와 같은 라이브러리와 언어는 병합 정렬의 변형을 사용하여 정렬 작업의 안정성을 보장하므로 개체 정렬 및 복잡한 데이터 구조에 특히 적합합니다.
결론
병합 정렬은 안정성, 일관된 성능 및 대규모 데이터 세트 정렬을 위한 적응성으로 인해 이론적인 컴퓨터 과학과 실제 응용 모두에서 계속해서 기본 알고리즘입니다. QuickSort와 같은 다른 알고리즘은 특정 상황에서 더 빠르게 수행될 수 있지만 Merge Sort는 보장된 O(n log n) 시간 복잡도와 다양성으로 인해 메모리가 제한된 환경과 동일한 키를 사용하여 요소의 순서를 유지하는 데 매우 유용합니다. 최신 프로그래밍 라이브러리에서의 역할은 실제 애플리케이션에서도 관련성을 유지하도록 보장합니다.
출처:
위 내용은 병합 정렬의 신비를 풀다: 정렬을 나누고 정복하기 위한 초보자 가이드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
