Merge Sort là một trong những thuật toán sắp xếp, độ khó phức tạp trung bình và đạt về hiệu quả thời gian, và hiệu năng. Do đó với những chương trình yêu cầu độ tối ưu cao thì Merge Sort là một lựa chọn tốt. Bài này chúng ta sẽ hiểu rõ hơn về Merge Sort và cách sử dụng bằng ngôn ngữ C++
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần bằng ngôn ngữ C++.
Mục lục bài viết
Tìm hiểu thuật toán Merge Sort
Giống như Quick sort, Merge sort là một thuật toán dùng để sắp xếp dãy số, và cũng chia nhỏ mảng ra nhiều mảng nhỏ để xử lý. Thuật toán này cũng chia mảng cần sắp xếp thành 2 nửa. Tiếp tục lặp lại việc này ở các nửa mảng đã chia. Sau cùng gộp các nửa đó thành mảng đã sắp xếp. Để gộp các nữa đó thành 1 mảng hoàn chỉnh, chúng ta sẽ sử dụng tiếp hàm merge() để gộp hai nửa mảng. Hàm merge(arr, l, m, r) là bước quan trọng nhất để gộp 2 nửa mảng thành 1 mảng.
Ví dụ các bước của thuật toán sắp xếp merge sort
Nếu bạn chưa hiểu tư tưởng của Merge sort. Đừng lo lắng, chúng ta sẽ đi đến ví dụ hình ảnh sau
Hình ảnh trên đây là ví dụ của thuật toán merge sort cho mảng {38, 27, 43, 3, 9, 82, 10}. Nếu nhìn kỹ hơn vào sơ đồ này, chúng ta thấy mảng ban đầu được tách ra nhỏ cho đến khi kích thước các mảng con la 1. Sau đó bắt đầu gộp lại cho đến khi được 1 mảng theo thứ tự tăng dần.
- Chúng ta có 1 mảng lớn là {38, 27, 43, 3, 9, 82, 10}.
- Tách ra làm 2 mảng nhỏ hơn là arr1 = [38 27 43 3] , arr2 = [9 82 10].
- Tách arr1 làm 2 mảng nhỏ hơn và arr 2 làm 2 mảng nhỏ hơn.
- Lặp đi lặp lại, đến khi mảng nhỏ nhất còn 1 phần tử.
- Bắt đầu ghép 2 các mảng lại với nhau sử dụng hàm Merge() theo thứ tự từ nhỏ tới lớn
- Sau cùng chúng ta có 1 mảng hoàn chỉnh theo thứ tự {3, 9, 10, 27, 38, 43, 82}
Vậy hàm merge() là hàm gì? và có thể ghép các chuỗi theo thứ tự
Dưới đây là code mẫu C++, chưa thuật toán hàm merge và sắp xếp theo thuật toán merge sorte
#include<stdlib.h>
#include<stdio.h>
// Gộp hai mảng con arr[l...m] và arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* Tạo các mảng tạm */
int L[n1], R[n2];
/* Copy dữ liệu sang các mảng tạm */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Gộp hai mảng tạm vừa rồi vào mảng arr*/
i = 0; // Khởi tạo chỉ số bắt đầu của mảng con đầu tiên
j = 0; // Khởi tạo chỉ số bắt đầu của mảng con thứ hai
k = l; // IKhởi tạo chỉ số bắt đầu của mảng lưu kết quả
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy các phần tử còn lại của mảng L vào arr nếu có */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy các phần tử còn lại của mảng R vào arr nếu có */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
/* l là chỉ số trái và r là chỉ số phải của mảng cần được sắp xếp */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Tương tự (l+r)/2, nhưng cách này tránh tràn số khi l và r lớn
int m = l+(r-l)/2;
// Gọi hàm đệ quy tiếp tục chia đôi từng nửa mảng
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* Hàm xuất mảng */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}
Ưu và nhược điểm của thuật toán Merge Sort:
- Ưu điểm: Sắp sếp nhanh hơn so với các thuật toán cơ bản (Insertion Sort, Selection Sort, Interchage Sort), và đôi khi nhanh hơn Quick Sort trong một số trường hợp.
- Nhược điểm: thuật toán khó cài đặt, không nhận dạng được mảng đã được sắp, nhìn chung khó hơn các thuật toán khác.
