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 [kiso.vn]

Ví dụ minh họa:

Merge sort algorithm png

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ử.

  1. 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()).
  2. 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.
  3. Trường hợp chỉ có một phần tử thì xem như đã được sắp xếp.
  4. 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.
  5. 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 Kiso.vn";
}

Kết quả:

sap xep chen mergesort PNG

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!!!

Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *