Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp trộn (Merge Sort)
Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp trộn (Merge Sort). Đây là một trong những thuật toán sắp xếp trong C++.
Chúng ta sẽ cùng nhau tìm hiều về sắp xếp trộn là gì và cách triển khai thuật toán sắp xếp trộn trong C++. Ở cuối bài viết, mình sẽ giải một bài toán cụ thể để các bạn hiểu hơn về cách áp dụng thuật toán trong thực tế.
1. Sắp xếp trộn là gì?
Sắp xếp trộn là một thuật toán sắp xếp dựa trên giải thuật Divide and Conquer (Chia để trị).
Thuật toán này sẽ chia mảng thành hai nữa rồi sắp xếp trên từng nữa một. Sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.
Bài viết này được đăng tại [free tuts .net]
Ví dụ minh họa:
Như các bạn đã thấy ở hình trên, dãy số ban đầu bao gôm các số: 38 27 43 3 9 82 10.
Chúng ta sẽ chia thành hai phần là một bên 4 số và một bên 3 số. Rồi tiếp tục chia 4 số đó thành hai phần là mỗi bên 2 số. Cứ chia như vậy cho đến khi được kết quả như dòng thứ 4.
Sau khi chia xong, bây giờ chúng ta bắt đầu vào việc so sanh từng phần nhỏ. Rồi gom chúng lại thành một dãy số hoàn chỉnh đã sắp xếp ở các dòng 5, 6, 7 như trong hình.
Sau khi gom lại và so sánh xong ta được dãy số mới đã sắp xếp: 3 9 10 27 38 43 82.
2. Thuật toán sắp xếp trộn (Merge Sort) trong C++
Trong phần này mình sẽ đưa ra các bước để viết thuật toán, sau đó mình sẽ để thuật toán đã viết sẵn cho các bạn dễ hình dung.
Giải thích thuật toán
Trong thuật toán sẽ có hai bước đó là chia phần tử và gộp phần tử (kèm theo sắp xếp). Cụ thể trong thuật toán mình viết hàm mergeSort() để chia phần tử và hàm merge() để gộp, sắp xếp phần tử.
- Sử dụng đệ qui để chia list thành hai nửa cho đến khi không chia thêm được nữa (hàm
mergeSorrt()). - Tạo hai mảng tạm thời để chứa các phần tử sau khi chia, cùng với đó là hai mảng con L và R.
- Trường hợp chỉ có một phần tử thì xem như đã được sắp xếp.
- Sau khi chia xong, sẽ gộp các phần tử ở mảng con R và L vào mảng chính arr.
- Kết hợp các list nhỏ đã sắp xếp với nhau thành một list mới. Sau khi kết hợp tiến hành sắp xếp chúng để tiếp tục cho lần kết hợp kế tiếp.
Code thuật toán sắp xếp trộn
Trong thuật toán mình đã chú thích cụ thể, các bạn có thể đọc để dễ hiểu hơn.
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];//tạo 2 mảng tạm thời để chứa các phần tử sau khi chia
// 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];
// khởi tạo các giá trị ban đầu
i = 0;
j = 0;
k = l;
//gộp hai mảng tạm thời vào mảng arr
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)
{
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);
}
}
3. Ví dụ sắp xếp trộn trong mảng
Chúng ta sẽ áp dụng thuật toán đã viết ở trên, để viết một chương trình sắp xếp các phần tử trong mảng được nhập từ bàn phím.
Tương tự như các bài trước, chỉ cần thay thế các thuật toán khác bằng thuật toán mergeSort() là được.
Code mẫu:
#include<stdlib.h>
#include<stdio.h>
#include <iostream>
using namespace std;
// Chúng ta cần có hai mảng con vì vậy cần tạo hai mảng con arr[l...m] và arr[m+1..r]. Sau đó gộp chúng lại
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];//tạo 2 mảng tạm thời để chứa các phần tử sau khi chia
// 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];
// khởi tạo các giá trị ban đầu
i = 0;
j = 0;
k = l;
//gộp hai mảng tạm thời vào mảng arr
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)
{
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 arr[], int size)
{
int i;
for (i=0; i < size; i++){
cout << arr[i];
cout<<"\t";
}
}
int main()
{
int n;
do{
cout << "\nNhập vào số lượng phần tử có trong mảng: ";
cin >> n;
}while(n <= 0);
int a[n];
for(int i = 0;i < n;i++){
cout<<"a["<<i<<"]=";
cin >> a[i];
};
cout<<"Mảng chưa được sắp xếp: \n";
printArray(a, n);
mergeSort(a, 0, n - 1);
cout<<"\nMảng sau khi được sắp xếp: \n";
printArray(a, n);
cout<<"\n---------------------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử trong mảng, sử dụng phương thức sắp xếp trộn. Cũng như kết thúc hướng dẫn thuật toán sắp xếp trộn trong C++. Chúc các bạn thực hiện thành công!!!
