Tìm hiểu thuật toán sắp xếp trộn merge sort với ví dụ bằng lập trình c++

Trong bài viết này Stanford sẽ giúp các bạn học lập trình hiểu rõ hơn về thuật toán sắp xếp trộn (merge sort) cũng như cài đặt thuật toán này qua ví dụ bằng lập trình c++.

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

Merge Sort là một thuật toán sắp xếp chia để trị (divide and conquer) với độ phức tạp thời gian là O(nlogn). Thuật toán này hoạt động bằng cách chia mảng cần sắp xếp thành hai nửa, sắp xếp từng nửa và sau đó gộp hai nửa đã sắp xếp lại với nhau.
Các bước thực hiện:

  • Chia mảng: Chia mảng thành hai nửa bằng nhau.
  • Sắp xếp đệ quy: Sắp xếp từng nửa bằng cách gọi đệ quy chính nó.
  • Gộp mảng: Gộp hai nửa đã sắp xếp lại với nhau để tạo thành mảng đã sắp xếp.


Minh họa bằng lập trình C++

Sau khi hiểu được ý tưởng của thuật toán sắp xếp trộn, tiếp theo chúng ta sẽ cài đặt thuật toán sắp xếp này bằng ngôn ngữ lập trình c++ như sau:

#include <vector>
using namespace std;
 
// Trộn 2 mảng con của arr[].
//Mảng con đầu tiên là arr[left..mid]
//Mảng con thứ hai là arr[mid+1..right]
void merge(vector<int>& arr, int left,
                     int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;
    //Tạo 2 danh sách
    vector<int> L(n1), R(n2);
    // Copy dữ liệu sang 2 vector tạm L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0;
    int k = left;
    // Merge the temp vectors back
    // into arr[left..right]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // Copy giá trị từ L[] sang lại mảng arr
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // Copy giá trị từ R[] sang lại mảng arr
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
//Hàm sắp xếp danh sách với chỉ số bên trái, phải của danh sách
void mergeSort(vector<int>& arr, int left, int right)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
 
//Hàm in thông tin
void printVector(vector<int>& arr)
{
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
int main()
{
    vector<int> arr = { 6, 5, 12, 10, 9, 1};
    int n = arr.size();
    cout << "Danh sach mang: \n";
    printVector(arr);
    mergeSort(arr, 0, n - 1);
    cout << "\nDanh sach mang sau khi sap xep: \n";
    printVector(arr);
    return 0;
}
Đầu ra:
1  5  6  9  10  12

Phân tích độ phức tạp của sắp xếp trộn
Độ phức tạp về thời gian:

  • Trường hợp tốt nhất: O(n log n), Khi mảng đã được sắp xếp hoặc gần được sắp xếp.
  • Trường hợp trung bình: O(n log n), Khi mảng được sắp xếp ngẫu nhiên.
  • Trường hợp xấu nhất: O(n log n), khi mảng được sắp xếp theo thứ tự ngược lại.

Không gian bổ sung: O(n), Cần có không gian bổ sung cho mảng tạm thời được sử dụng trong quá trình hợp nhất.
Ứng dụng của sắp xếp trộn:

  • Sắp xếp các tập dữ liệu lớn
  • Sắp xếp bên ngoài (khi tập dữ liệu quá lớn không thể chứa trong bộ nhớ)
  • Đây là thuật toán được ưu tiên để sắp xếp các danh sách liên kết.
  • Có thể dễ dàng song song hóa vì chúng ta có thể sắp xếp các mảng con một cách độc lập và sau đó hợp nhất.
  • Hàm merge của thuật toán sắp xếp merge giúp giải quyết hiệu quả các vấn đề như hợp và giao của hai mảng đã được sắp xếp.

Ưu điểm và nhược điểm của sắp xếp trộn
Thuận lợi

  • Tính ổn định : Thuật toán sắp xếp trộn là thuật toán sắp xếp ổn định, nghĩa là nó duy trì thứ tự tương đối của các phần tử bằng nhau trong mảng đầu vào.
  • Đảm bảo hiệu suất trong trường hợp xấu nhất: Thuật toán sắp xếp trộn có độ phức tạp thời gian trong trường hợp xấu nhất là O(N logN) nghĩa là nó hoạt động tốt ngay cả trên các tập dữ liệu lớn.
  • Dễ thực hiện: Phương pháp chia để trị rất đơn giản.
  • Song song tự nhiên : Chúng tôi độc lập hợp nhất các mảng con khiến nó phù hợp cho việc xử lý song song.

Nhược điểm

  • Độ phức tạp về không gian: Thuật toán sắp xếp trộn yêu cầu thêm bộ nhớ để lưu trữ các mảng con đã hợp nhất trong quá trình sắp xếp.
  • Không tại chỗ: Merge Sort không phải là thuật toán sắp xếp tại chỗ, nghĩa là nó cần thêm bộ nhớ để lưu trữ dữ liệu đã sắp xếp.
  • Điều này có thể là một bất lợi trong các ứng dụng mà việc sử dụng bộ nhớ là mối quan tâm.
  • Nhìn chung, Merge Sort chậm hơn QuickSort vì QuickSort thân thiện với bộ nhớ đệm hơn vì nó hoạt động tại chỗ.

Như vậy qua bài viết này, Stanford đã giúp các bạn học lập trình hiểu hơn về thuật toán sắp trộn (merge sort) cũng như cài đặt thuật toán bằng lập trình c++. Để hiểu rõ hơn thuật toán này bạn có thể lập trình theo hướng dẫn trong bài viết này nhé. Bạn có thể tìm hiểu các thuật toán sắp xếp trong lập trình ở đây. Chúc các bạn thành công !

Bên cạnh đó bạn có thể bắt đầu ngay con đường chinh phục trở thành lập trình viên chuyên nghiệp trong tương lai của mình bằng việc đăng ký tham gia khoá học lập trình tại đây: http://bit.ly/2SLPYFF. Hoặc gọi ngay cho Stanford theo hotline: 0963.723.236 - 0866.586.366 để được gọi lại tư vấn trực tiếp nhé.

==========🎬 🎬 🎬==========
☎️STANFORD – ĐÀO TẠO VÀ PHÁT TRIỂN CÔNG NGHỆ
Hotline: 0963 723 236 - 0866 586 366
Website: https://stanford.com.vn
Facebook: https://www.facebook.com/Stanford.com.vn
Youtube: http://bit.ly/2TkKT7I

Tags: thuật toán sắp xếp trộn merge sort, sắp xếp trộn bằng c++