MERGE SORT: Thuật toán sắp xếp trộn

Ngày đăng: 09/09/2020   -    Cập nhật: 23/10/2020

Trong khoa học máy tính, thuật toán MERG SORT (sắp xếp trộn) là một thuật toán được sử dụng để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự) theo một trật tự nào đó.

Nó được xếp vào thể loại sắp xếp so sánh.

Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945.


1. Thuật toán MERGE SORT là gì?


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

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

Thuật toán Merge Sort là một trong những thuật toán có độ phức tạp ở mức trung bình và cùng sử dùng phương pháp chia để trị giống thuật toán sắp xếp nhanh Quick Sort.

Thuật toán này không chỉ áp dụng trong sắp xếp mà còn ở nhiều bài toán khác.

Ý tưởng của giải thuật này bắt nguồn từ việc trộn 2 danh sách đã sắp xếp thành 1 danh sách mới cũng được sắp xếp.

Giả sử có hai danh sách đã được sắp xếp a[1 ... m]b[1 ... n].

Ta có thể trộn chúng lại thành một danh sách mới c[1 ... m+n] được sắp xếp theo cách sau:


  • So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho vào danh sách mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là rỗng.
  • Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách kia cho vào cuối danh sách mới.

Độ  phức tạp thuật toán: O(nlog(n))

2. Ý tưởng và Mô tả thuật toán Merge sort


Ý tưởng để áp dụng cho một Merge Sort được mô tả ngắn gọn như trong code giả bên dưới:


// mergeSort(arr[], l,  r)
// if r > l
//      1. Tìm chỉ số nằm giữa mảng để chia mảng thành 2 nửa:
//              middle m = (l+r)/2
//      2. Gọi đệ quy hàm mergeSort cho nửa đầu tiên:  
//              mergeSort(arr, l, m)
//      3. Gọi đệ quy hàm mergeSort cho nửa thứ hai:
//              mergeSort(arr, m+1, r)
//      4. Gộp 2 nửa mảng đã sắp xếp ở (2) và (3):
//              merge(arr, 1, m, r)
 

Để giúp bạn hình dung rõ hơn, đây là sơ đồ minh họa tiến trình từng bước của thuật toán Merge sort áp dụng cho mảng {25, 30, 45, 6, 11, 90, 15}

Sơ đồ minh họa thuật toán Merge Sort

Sơ đồ minh họa thuật toán Merge Sort

Nếu nhìn kỹ hơn vào sơ đồ này, chúng ta có thể thấy:

  • Mảng ban đầu được lặp lại hành động chia cho tới khi kích thước các mảng sau chia là 1.
  • Khi kích thước các mảng con là 1, tiến trình gộp sẽ bắt đầu.
  • Thực hiện gộp lại các mảng này cho tới khi hoàn thành và chỉ còn một mảng đã sắp xếp.


3. Triển khai thuật toán Merge sort trong Java


Như các bài chia sẻ trước, chung ta đã có ý tưởng và giải thuật rồi. Bây giờ hãy cùng mình triển khai thuật toán Merge sort này trong Java xem như thế nào nhé.


package merge.sort.algo;

public class MergeSort {

    // Merge hai mảng con của arr[].
    // Mảng con thứ nhất là arr[l..m]
    // Mảng con thứ hai là arr[m+1..r]
    void merge(int arr[], int lint mint r) {

        // Tìm kích thước của 2 mảng con để merged
        int n1 = m - l + 1;
        int n2 = r - m;

        // Tạo mảng tạm
        int L[] = new int[n1];
        int R[] = new int[n2];

        // Copy dữ liệu vào mảng tạm
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        // Merge các mảng tạm lại

        // Chỉ mục ban đầu của 2 mảng con
        int i = 0, j = 0;

        // Chỉ mục ban đầu của mảng phụ được hợp nhất
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Sao chép các phần tử còn lại của L[] nếu có
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Sao chép các phần tử còn lại của R[] nếu có
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    void sort(int arr[], int lint r) {
        if (l < r) {

            // Tìm điểm chính giữa
            int m = (l + r) / 2;

            // Hàm đệ quy tiếp tục chia đôi
            sort(arr, l, m);
            sort(arr, m + 1, r);

            merge(arr, l, m, r);
        }
    }

    // In các phần tử của mảng
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    public static void main(String args[]) {
        int arr[] = { 2530456119015 };

        System.out.println("Mảng ban đầu:");
        printArray(arr);

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0arr.length - 1);

        System.out.println("Mảng sau khi sắp xếp:");
        printArray(arr);
    }
}
 


Khi chạy chương trình, ta nhận được kết quả là:



Mảng ban đầu
25 30 45 6 11 90 15
Mảng sau khi sắp xếp:
6 11 15 25 30 45 90
 


Merge Sort là một trong những thuật toán sắp xếp nhanh được sử dụng rộng rãi.

Giả sử có một máy tính giải được 109 bài toán trong 1 giây:


  • Trong trường hợp đó, để sắp xếp một dãy số gồm 106 số thì Merge Sort tốn chưa tới 1 giây

Ngoài ra, Merge Sort còn có tốc độ ổn định.

Vẫn là một máy tính giải được 109 bài toán trong 1 giây:


  • Trong khi đó nếu ta dùng Quick Sort sắp xếp 1 dãy chứa 106 số thì vẫn có trường hợp ta phải chờ 1000 giây để sắp xếp xong
  • Còn Merge Sort thì luôn luôn chưa tới 1 giây.

Như bạn thấy đó, sử dụng đúng thuật toán mang lại hiệu quả cực kỳ lớn.

> Đây cũng chính là điểm khác nhau của Lập trình viên "THƯỜNG" và Lập trình viên "GIỎI". Nếu bạn là người mới và muốn trở thành một Lập trình viên giỏi thì hãy tham gia HỌC LẬP TRÌNH (Full Stack) ngay hôm nay!

Không chỉ mang lại tốc độ cực kỳ tốt, Merge Sort còn giữ được thứ tự của các phần tử bằng nhau sau khi sắp xếp.

Chẳng hạn như khi ta cần sắp xếp một mảng gồm các điểm theo trong hệ tọa độ Oxy theo chiều tăng dần của hoành độ x, nếu hoành độ bằng nhau thì sắp tăng dần theo tung độ y.

Trong trường hợp đó, ta chỉ cần dùng Merge Sort sắp xếp tung độ sau đó lại dùng Merge Sort sắp xếp hoành độ.

Thuật toán Merge sort là một giải thuật sắp xếp mà có thời gian thực hiện là O(NlogN) trong mọi trường hợp.

Chính vì thế, với dữ liệu lớn và cần ít thao tác sắp xếp thì Merge Sort sẽ tối ưu hơn Quick sort. Nó chỉ có 1 nhược điểm đó là code hơi khó cài đặt.

Nhưng bạn đã có bài viết này sử dụng để tham khảo. Hãy luyện tập và luyện tập, qua nhiều lần thì chắc chắn bạn sẽ nắm được thuật toán Merge sort thôi.


---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học làm Lập trình viên. Hành động ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0914939543
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
 
#niit #niithanoi #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #java #php #python
Bình luận Facebook
Đăng ký tư vấn
Nhân viên gọi điện tư vấn miễn phí sau khi đăng ký
Được cập nhật các ưu đãi sớm nhất
Hotline: 0383180086
Tên không được để trống
Số điện thoại không được để trống
Email không được để trống
Hãy đăng ký để nhận những thông tin mới nhất về học bổng mới nhất tại NIIT - ICT Hà Nội
top
Đóng lại Đăng ký học tại NIIT - ICT Hà Nội
6260+ học viên đã theo học tại NIIT - ICT Hà Nội và có việc làm tốt trong ngành lập trình. Nắm lấy cơ hội ngay hôm nay!
Chọn khóa học
  • KHÓA HỌC LẬP TRÌNH FRONT END VỚI REACT.JS
  • KHÓA HỌC LẬP TRÌNH PHP WEB
  • Khóa học PHP Full stack [2023] cho người mới bắt đầu
  • Khóa học BIG DATA với Hadoop và Spark
  • Khóa học Lập trình Android tại Hà Nội
  • [Tuyển sinh 2023] Lập trình viên Quốc tế DigiNxt
  • Khóa học Tiền lương & Phúc lợi (C&B Excel) tại Hà Nội
  • LẬP TRÌNH GAME
    • Khóa học Lập trình Game Unity
  • LẬP TRÌNH WEB FRONT END
    • KHÓA HỌC PYTHON HƯỚNG ĐỐI TƯỢNG
    • KHÓA HỌC ANGULAR & TYPESCRIPT (FRONT END)
  • LẬP TRÌNH WEB BACK END
    • LẬP TRÌNH JAVA WEB VỚI FRAME WORK
    • Lập trình Web với Django
    • Lập trình PHP với Laravel Framework
  • CHƯƠNG TRÌNH ĐÀO TẠO ỨNG DỤNG CÔNG NGHỆ
    • Khóa học Tiền lương & Phúc lợi (C&B Excel) tại TP HCM
  • LẬP TRÌNH WEB FULL STACK
    • Khóa học Java Full stack (IJFD)
  • LẬP TRÌNH MOBILE
    • FRONT-END VỚI REACTJS VÀ REACT NATIVE
    • Lập trình Android Nâng cao
  • ĐÀO TẠO CHO DOANH NGHIỆP
    • KHÓA HỌC BUSINESS ANALYSIC TỪ CƠ BẢN ĐẾN NÂNG CAO 2023
    • Khóa học Magento: Làm chủ CMS TMĐT lớn nhất
    • Khóa học IOT: Xây dựng Sản phẩm IOT với Raspberry Pi
    • Khóa học Automation Testing Chuyên nghiệp
  • KHÓA HỌC DỰ ÁN
    • Học sử dụng bộ Office: Word, Excel, Power Point, Mail chuyên nghiệp
  • KHÓA HỌC KHÁC
    • VBA Excel Toàn Tập (Cơ Bản - Nâng Cao)
    • VBA Excel Nâng cao
    • Khóa học JMeter: Performance Testing
    • Khóa học Tester đạt chuẩn Quốc tế ISTQB Foundation Level
    • Khoá Học Tester đạt chuẩn quốc tế ISTQB Advanced Level
Bạn chưa chọn khóa học cần đăng ký
Tên không được để trống
Số điện thoại không được để trống
Email không được để trống
Đăng ký học thành công!
Cảm ơn bạn đã đăng ký học tại NIIT - ICT HÀ NỘI!