Thuật Toán Merge Sort(Sắp Xếp Trộn) - Poki Mobile
Có thể bạn quan tâm
Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp merge sort. Đây là một thuật toán rất sắp xếp rất hay và có độ phức tạp thấp hơn.
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu
Bạn đang đọc: Thuật toán merge sort(Sắp xếp trộn)
Ý tưởng của thuật toán merge sort
Giống như Quick sort, Merge sort là một thuật toán chia để trị. Thuật toán này chia mảng cần sắp xếp thành 2 nửa. Tiếp tục lặp lại việc này ở những nửa mảng đã chia. Sau cùng gộp những nửa đó thành mảng đã sắp xếp. Hàm merge ( ) được sử dụng để gộp hai nửa mảng. Hàm merge ( arr, l, m, r ) là tiến trình quan trọng nhất sẽ gộp hai nửa mảng thành 1 mảng sắp xếp, những nửa mảng là arr [ l … m ] và arr [ m + 1 … r ] sau khi gộp sẽ thành một mảng duy nhất đã sắp xếp . Hãy xem ý tưởng sáng tạo tiến hành code dưới đây để hiểu hơn
01234567891011 mergeSort ( arr [ ], l, r )If r > l1. Tìm chỉ số nằm giữa mảng để chia mảng thành 2 nửa :middle m = ( l + r ) / 22. Gọi đệ quy hàm mergeSort cho nửa tiên phong :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, l, m, r ) Hình ảnh dưới đây từ wikipedia sẽ hiển thị cho bạn hàng loạt sơ đồ tiến trình của thuật toán merge sort cho mảng { 38, 27, 43, 3, 9, 82, 10 }. Nếu nhìn kỹ hơn vào sơ đồ này, tất cả chúng ta hoàn toàn có thể thấy mảng khởi đầu được lặp lại hành vi chia cho tới khi kích cỡ những mảng sau chia là 1. Khi kích cỡ những mảng con là 1, tiến trình gộp sẽ mở màn triển khai gộp lại những mảng này cho tới khi hoàn thành xong và chỉ còn một mảng đã sắp xếp .
Cách hàm merge hoạt động khi gộp hai mảng con
Với trường hợp khi 2 mảng con chỉ có 1 thành phần, ta chỉ việc xem thành phần nào nhỏ hơn và đẩy lên đầu, thành phần còn lại đặt phía sau. Do vậy, những mảng con cần gộp lại có đặc thù luôn được sắp tăng dần .
0123456789101112131415161718192021 Giả sử ta có 2 mảng con lần lượt là :arr1 = [ 1 9 10 10 ], n1 = 4 / / chiều dài của mảng conarr2 = [ 3 5 7 9 ], n2 = 4sort_arr = [ ] / / Mảng lưu lại tiến trình gộpKhởi tạo i = 0, j = 0 tương ứng là chỉ số khởi đầu của arr1 và arr2Xét thấy arr1 [ i ] < arr2 [ j ] => chèn arr1 [ i ] vào cuối mảng sort_arr, tăng i lên 1 đơn vị chức năng=> sort_arr = [ 1 ], i = 1Xét thấy arr1 [ i ] > arr2 [ j ] => chèn arr2 [ j ] vào cuối mảng sort_arr, tăng j lên 1 đơn vị chức năng=> sort_arr = [ 1, 3 ], i = 1, j = 1Xét thấy arr1 [ i ] > arr2 [ j ] => chèn arr2 [ j ] vào cuối mảng sort_arr, tăng j lên 1 đơn vị chức năng=> sort_arr = [ 1, 3, 5 ], i = 1, j = 2Xét thấy arr1 [ i ] > arr2 [ j ] => chèn arr2 [ j ] vào cuối mảng sort_arr, tăng j lên 1 đơn vị chức năng=> sort_arr = [ 1, 3, 5, 7 ], i = 1, j = 3Xét thấy arr1 [ i ] = arr2 [ j ] => chèn arr1 [ i ] hoặc arr2 [ j ] vào cuối mảng sort_arrGiả sử tôi chọn arr1, tăng i lên 1 đơn vị chức năng=> sort_arr = [ 1, 3, 5, 7, 9 ], i = 2, j = 3Xét thấy arr1 [ i ] > arr2 [ j ] => chèn arr2 [ j ] vào cuối mảng sort_arr, tăng j lên 1 đơn vị chức năng=> sort_arr = [ 1, 3, 5, 7, 9, 9 ], i = 1, j = 4Do j > = n2, liên tục tăng i chừng nào i < n1 thi thêm thành phần ở arr1 [ i ] ư vào sort_arr .Sau cùng ta được mảng đã sắp xếp là sort_arr = [ 1, 3, 5, 7, 9, 9, 10, 10 ] Xem thêm : Chuyên mục cấu trúc tài liệu và giải thuật
Minh họa thuật toán sắp xếp quick sort sử dụng C/C++
0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
/ / Code from https://pokimobile.vn
#include
#include
/ / Gộp hai mảng con arr [ l … m ] và arr [ m + 1 .. r ]
voidmerge(intarr[],intl,intm,intr)
{
inti,j,k;
intn1=m-l+1;
intn2=r-m;
/ * Tạo những mảng tạm * /
intL[n1],R[n2];
/ * Copy dữ liệu sang những mảng tạm * /
for(i=0;i
Từ khóa » độ Phức Tạp Thuật Toán Merge Sort
-
Thuật Toán Merge Sort - Giới Thiệu Chi Tiết Và Code Ví Dụ Trên Nhiều ...
-
Thuật Toán Sắp Xếp Merge Sort - Viblo
-
Độ Phức Tạp Của Thuật Toán Merge Sort
-
Bài 4 Độ Phức Tạp Của Thuật Toán Merge Sort (Sắp Xếp Trộn), Độ ...
-
Độ Phức Tạp Của Thuật Toán Merge Sort? - Tạo Website
-
Phân Tích Thuật Toán Merge Sort - Stream Hub
-
Thuật Toán Merge Sort(Sắp Xếp Trộn) - Lập Trình Không Khó
-
Bài 4 Độ Phức Tạp Tính Toán: Merge Sort - YouTube
-
Thuật Toán Sắp Xếp Trộn (Merge Sort) - TEK4
-
Sắp Xếp Trộn – Wikipedia Tiếng Việt
-
Thuật Toán Sắp Xếp Trộn - Merge Sort | Học JavaScript
-
Merge Sort - Giải Thuật Lập Trình
-
Thuật Toán Sắp Xếp Trộn - Merge Sort Algorithm C/C++
-
Thuật Toán Merge Sort – Sắp Xếp Trộn - Đào Tạo Tin Học Trực Tuyến