SẮP XẾP & TÌM KIẾM
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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

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.

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.

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 Freetuts.net";
}

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

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top