Rate this post

Merge sort là một thuật toán sắp xếp theo kiểu chia để trị, nó sắp xếp một dãy số bằng cách chia nó thành hai dãy con, sau đó sắp xếp và hợp nhất hai dãy con đó thành một dãy được sắp xếp hoàn chỉnh.

Các bài viết liên quan

Cụ thể, merge sort bắt đầu bằng việc chia dãy số thành hai phần bằng nhau. Nếu dãy có ít hơn 2 phần tử, nó được coi là đã được sắp xếp. Sau đó, hai dãy con được sắp xếp đệ quy bằng cách gọi merge sort cho chúng. Cuối cùng, hai dãy con được hợp nhất thành một dãy được sắp xếp hoàn chỉnh.

Ví dụ:

Trong đó : mergeSort là hàm đệ quy để sắp xếp, merge là hàm hợp nhất hai dãy con đã sắp xếp.

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

Merge sort là một thuật toán sắp xếp rất hiệu quả với thời gian chạy trung bình và tốt nhất là O(n log n), nó rất tốt cho việc sắp xếp các dãy dữ liệu lớn và chưa được sắp xếp. Nó cũng là một thuật toán sắp xếp không giới hạn bởi kích thước dãy và có thể sử dụng trên cả dãy dữ liệu số và chuỗi. Tuy nhiên, merge sort cần sử dụng thêm bộ nhớ để lưu trữ các dãy con và tổng hợp chúng, do đó nó không phù hợp cho việc sắp xếp trên dãy dữ liệu rất lớn với bộ nhớ hạn chế.

Ưu điểm merge sort c++

Merge Sort là một thuật toán sắp xếp theo kiểu chia để trị, nó sắp xếp một dãy số bằng cách chia nó thành hai dãy con, sau đó sắp xếp và hợp nhất hai dãy con đó thành một dãy được sắp xếp hoàn chỉnh.
Merge Sort có thời gian chạy trung bình và tốt nhất là O(n log n), nó rất tốt cho việc sắp xếp các dãy dữ liệu lớn và chưa được sắp xếp.
Merge sort là một thuật toán sắp xếp không giới hạn bởi kích thước dãy và có thể sử dụng trên cả dãy dữ liệu số và chuỗi.
Merge sort là một thuật toán sắp xếp độc lập với giá trị dãy dữ liệu, nó có thể sắp xếp các dãy dữ liệu có giá trị bất kỳ.
Merge sort là một thuật toán sắp xếp “đồng nhất” vì nó không thay đổi thứ tự của các phần tử bằng nhau.
Merge sort có thể dễ dàng được sử dụng trong việc tổng hợp hai hoặc nhiều dãy dữ liệu được sắp xếp.

ví dụ về sử dụng merge sort c++

Ví dụ 1: Sắp xếp mảng số nguyên

Copy code#include <iostream>
using namespace std;

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];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Dãy số trước khi sắp xếp: \n";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
    cout << endl;
    mergeSort(arr, 0, arr_size - 1);
    cout << "Dãy số sau khi sắp xếp: \n";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i];
}

Ví dụ 2: Sắp xếp mảng chuỗi

#include <iostream>
#include <string>
using namespace std;

void merge(string arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    string L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i].compare(R[j]) <= 0)
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(string arr[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main()
{
    string arr[] = {"apple", "banana", "cherry", "date", "elderberry"};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Dãy chuỗi trước khi sắp xếp: \n";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
    cout << endl;
    mergeSort(arr, 0, arr_size - 1);
    cout << "Dãy chuỗi sau khi sắp xếp: \n";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
    return 0;
}

Trong hai ví dụ trên, hàm mergeSort và merge được sử dụng để sắp xếp mảng số nguyên và mảng chuỗi. Hàm mergeSort đệ quy gọi đến hàm merge để hợp, tổng hợp các dãy con đã được sắp xếp thành một dãy sắp xếp hoàn chỉnh.

Các bạn có thể thử chạy ví dụ trên và thay đổi giá trị của mảng đầu vào để thấy hiệu quả của thuật toán merge sort trong C++.

Algorithm, C/C++

merge sort trong c++ là gì

Ưu điểm merge sort c++

ví dụ về sử dụng merge sort c++

Trả lời Hủy