Thuật toán sắp xếp trộn (Merge Sort) – Freetuts

Posted on Updated on by adminChuyên mục:Kiến thức Internet

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

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau tìm hiều về sắp xếp trộn là gì và cách tiến hành 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 đơn cử để những bạn hiểu hơn về cách vận dụng thuật toán trong trong thực tiễn .

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 đó tích hợp chúng lại với nhau thành một mảng đã được sắp xếp .

Ví dụ minh họa:

Merge sort algorithm png

Như những bạn đã thấy ở hình trên, dãy số bắt đầu bao gôm những 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 liên 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 tác dụng như dòng thứ 4 .
Sau khi chia xong, giờ đây tất cả chúng ta mở màn 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 hảo đã sắp xếp ở những 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 những bước để viết thuật toán, sau đó mình sẽ để thuật toán đã viết sẵn cho những bạn dễ tưởng tượng .

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 đơn cử, những bạn hoàn toà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ẽ vận dụng thuật toán đã viết ở trên, để viết một chương trình sắp xếp những thành phần 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
#include
#include 
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["<> 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ả:

sap xep chen mergesort PNG

Như vậy là tất cả chúng ta đã thực thi xong chương trình sắp xếp những thành phần trong mảng, sử dụng phương pháp 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 những bạn thực thi thành công xuất sắc ! ! !

admin