Kỹ thuật sắp xếp hợp nhất dựa trên kỹ thuật chia và chinh phục. Chúng tôi chia tập dữ liệu while thành các phần nhỏ hơn và hợp nhất chúng thành một phần lớn hơn theo thứ tự được sắp xếp. Nó cũng rất hiệu quả đối với các trường hợp xấu nhất vì thuật toán này có độ phức tạp về thời gian thấp hơn đối với trường hợp xấu nhất.
Sự phức tạp của Kỹ thuật Sắp xếp Hợp nhất
-
Độ phức tạp về thời gian:O (n log n) cho mọi trường hợp
-
Độ phức tạp của không gian:O (n)
Input − The unsorted list: 14 20 78 98 20 45 Output − Array after Sorting: 14 20 20 45 78 98
Thuật toán
hợp nhất (mảng, trái, giữa, phải)
Đầu vào :Mảng tập dữ liệu, chỉ mục trái, giữa và phải
Đầu ra :Danh sách đã hợp nhất
Begin
nLeft := m - left+1
nRight := right – m
define arrays leftArr and rightArr of size nLeft and nRight respectively
for i := 0 to nLeft do
leftArr[i] := array[left +1]
done
for j := 0 to nRight do
rightArr[j] := array[middle + j +1]
done
i := 0, j := 0, k := left
while i < nLeft AND j < nRight do
if leftArr[i] <= rightArr[j] then
array[k] = leftArr[i]
i := i+1
else
array[k] = rightArr[j]
j := j+1
k := k+1
done
while i < nLeft do
array[k] := leftArr[i]
i := i+1
k := k+1
done
while j < nRight do
array[k] := rightArr[j]
j := j+1
k := k+1
done
End mergeSort (mảng, trái, phải)
Đầu vào :Một mảng dữ liệu và giới hạn dưới và trên của mảng
Đầu ra :Mảng được sắp xếp
Begin
if lower < right then
mid := left + (right - left) /2
mergeSort(array, left, mid)
mergeSort (array, mid+1, right)
merge(array, left, mid, right)
End Mã mẫu
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void merge(int *array, int l, int m, int r) {
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
//marge temp arrays to real array
while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i];
i++;
}else{
array[k] = rarr[j];
j++;
}
k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i];
i++; k++;
}
while(j<nr) { //extra element in right array
array[k] = rarr[j];
j++; k++;
}
}
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
mergeSort(arr, 0, n-1); //(n-1) for last index
cout << "Array after Sorting: ";
display(arr, n);
} Đầu ra
Enter the number of elements: 6 Enter elements: 14 20 78 98 20 45 Array before Sorting: 14 20 78 98 20 45 Array after Sorting: 14 20 20 45 78 98