병합 정렬
병합 정렬은 가장 인기 있고 효율적인 정렬 알고리즘 중 하나입니다. 분할 및 정복 알고리즘의 원리를 기반으로합니다. 배열을 개별 요소로 나눌 때까지 반복적으로 배열을 두 개로 나누는 방식으로 작동합니다. 개별 요소는 그 자체로 정렬 된 배열입니다. 병합 정렬은 이러한 작은 정렬 된 배열을 반복적으로 병합하여 하나의 최종 정렬 된 배열을 얻을 때까지 더 큰 정렬 된 하위 배열을 생성합니다. 전자 상거래 응용 프로그램에서 널리 사용됩니다.
병합 정렬 알고리즘
하향식 병합 정렬 접근 방식은 전체 배열을 사용하여 맨 위에서 시작하여 재귀를 사용하여 개별 요소까지 아래쪽으로 진행합니다.
n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정합니다.
MergeSort()
-
두 개의 변수
beg와end를 취하고 시작 요소와 끝 요소의 인덱스를 저장합니다. -
공식
mid =(mid+end)/2를 사용하여 배열의 중간 지점을 찾아 두 개의 반으로 나눕니다. -
배열을
arr[beg, ...., mid]와arr[mid + 1, ...., end]두 부분으로 나눕니다. -
재귀를 사용하여 배열을 단일 요소로 하위 배열로 반복적으로 나눕니다.
-
병합 함수를 호출하여 정렬 된 배열 작성을 시작합니다.
Merge()
-
정렬 된 출력을 저장하기 위해 보조 배열 ‘출력’을 초기화합니다.
-
3 개의 포인터
i,j&k를 초기화합니다.i는 첫 번째 하위 배열beg의 시작을 가리 킵니다.
j는 두 번째 하위 배열mid + 1의 시작을 가리 킵니다.
beg로 초기화 된k는 정렬 된 배열 ‘출력’의 현재 인덱스를 유지합니다. -
arr[beg, ...., mid]또는arr[mid + 1, ...., end]하위 배열의 끝에 도달 할 때까지 요소 중에서 더 작은 값을 선택합니다. 인덱스i&j에서output에 삽입합니다. -
나머지 요소를 선택하고 배열 중 하나가 소진되면
output에 삽입합니다. -
output을arr[beg, ..., end]에 복사합니다.
병합 정렬 예
배열이(5,3,4,2,1,6)이라고 가정합니다. 병합 정렬 알고리즘을 사용하여 정렬합니다.
| 동작 | (5,3,4,2,1,6) |
mergesort(0,5) |
|---|---|---|
divide |
(5,3,4) (2,1,6) |
mergesort(0,2) mergesort(3,5) |
divide |
(5,3) (4) (2,1) (6) |
mergesort(0,1) mergesort(2,2) mergesort(3,4) mergesort(5,5) |
divide |
(5) (3) (4) (2) (1) (6) |
개별 요소로 분리 된 배열 |
merge |
(3,5) (4) (1,2) (6) |
merge(0,1) merge(2,2) merge(3,4) merge(5,5) |
merge |
(3,4,5) (1,2,6) |
merge(0,2) merge(3,5) |
merge |
(1,2,3,4,5,6) |
merge(0,5) |
정렬 된 배열을 얻습니다-(1 2 3 4 5 6)
병합 정렬 알고리즘 구현
#include <iostream>
using namespace std;
void merge(int arr[], int beg, int mid, int end) {
int output[end - beg + 1];
int i = beg, j = mid + 1, k = 0;
// add smaller of both elements to the output
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
output[k] = arr[i];
k += 1;
i += 1;
} else {
output[k] = arr[j];
k += 1;
j += 1;
}
}
// remaining elements from first array
while (i <= mid) {
output[k] = arr[i];
k += 1;
i += 1;
}
// remaining elements from the second array
while (j <= end) {
output[k] = arr[j];
k += 1;
j += 1;
}
// copy output to the original array
for (i = beg; i <= end; i += 1) {
arr[i] = output[i - beg];
}
}
void mergeSort(int arr[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
// divide and conquer
mergeSort(arr, beg, mid); // divide : first half
mergeSort(arr, mid + 1, end); // divide: second half
merge(arr, beg, mid, end); // conquer
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
mergeSort(arr, 0, n - 1); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
병합 정렬 알고리즘 복잡성
시간 복잡성
- 평균 사례
병합 정렬은 재귀 알고리즘입니다. 다음 반복 관계는 병합 정렬에 대한 시간 복잡도 표현식을 제공합니다.
T(n) = 2T(n/2) + θ(n)
이 반복 관계의 결과는T(n) = nLogn이되며, n 크기의 배열이 최대logn 부분으로 나뉘어져 있고 각 부분의 병합은O(n)을 취하는 것으로 볼 수도 있습니다. 시각.
따라서 시간 복잡도는 [Big Theta] :O(nLogn)의 순서입니다.
- 최악의 경우
최악의 시간 복잡도는 [Big O] :O(nLogn)입니다.
- 베스트 케이스
최적의 시간 복잡도는 [Big Omega] :O(nLogn)입니다. 최악의 시간 복잡성과 동일합니다.
공간 복잡성
정렬 된 하위 배열을 보조 배열에 저장하려면 n개의 보조 공간이 필요하기 때문에 병합 정렬 알고리즘의 공간 복잡성은 O(n)입니다.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn