Sắp Xếp Trộn – Wikipedia Tiếng Việt
Có thể bạn quan tâm
Phân loại | Giải thuật sắp xếp |
---|---|
Cấu trúc dữ liệu | Khác nhau |
Hiệu suất trường hợp tệ nhất | Trung bình |
Độ phức tạp không gian trường hợp tệ nhất | Cần vùng nhớ trung gian khác nhau tùy loại |
Tối ưu | Thỉnh thoảng |
Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để 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ự, v.d. luồng tập tin) 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]. Một thuật toán chi tiết được Goldstine và Neumann đưa ra năm 1948.[2]
Trộn
[sửa | sửa mã nguồn]Giả sử có hai danh sách đã được sắp xếp và . Ta có thể trộn chúng lại thành một danh sách mới đượ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.
Ví dụ: Cho hai danh sách , quá trình hòa nhập diễn ra như sau:
Danh sách a | Danh sách b | So sánh | Danh sách c |
---|---|---|---|
1,3,7,9 | 2,6 | 1<2 | 1 |
3,7,9 | 2,6 | 2<3 | 1,2 |
3,7,9 | 6 | 3<6 | 1,2,3 |
7,9 | 6 | 6<7 | 1,2,3,6 |
7,9 | 1,2,3,6,7,9 |
Trộn tại chỗ
[sửa | sửa mã nguồn]Giả sử trong danh sách có 2 danh sách con kề nhau và đã được sắp. Ta áp dụng cách trộn tương tự như trên để trộn hai danh sách con vào một danh sách tạm rồi trả lại các giá trị của danh sách tạm T về danh sách A. Làm như vậy gọi là trộn tại chỗ.
Trộn từ dưới lên
[sửa | sửa mã nguồn]Nếu danh sách con chỉ gồm hai phần tử, mỗi nửa của nó gồm một phần tử đương nhiên đã được sắp. Do đó việc trộn tại chỗ hai nửa danh sách này cho danh sách con 2 phân tử được sắp.
Xuất phát từ đầu danh sách ta trộn với , với ,... Khi đó mọi danh sách con gồm hai phần tử của đã được sắp. Tiếp tục trộn các danh sách con kế tiếp nhau gồm 2 phần tử thành các danh sách con 4 phần tử... Mỗi lần trộn số các danh sách con cần trộn giảm đi một nửa. Quá trình dừng lại khi số danh sách con chỉ còn một.
Ví dụ: Cho danh sách
Công việc | Số DS con | Kết quả |
---|---|---|
Trộn các phần tử đứng kề nhau | 7 | 2,3-5,6-1,4-7 |
Trộn các danh sách con 2 phần tử kề nhau | 4 | 2,3,5,6-1,4,7 |
Trộn các danh sách con 4 phần tử kề nhau | 2 | 1,2,3,4,5,6,7 |
Sắp xếp trộn đệ quy
[sửa | sửa mã nguồn]Một cách gọi đệ quy của sắp xếp trộn cũng thường được hướng dẫn trong các giáo trình giải thuật.
Để sắp xếp trộn đoạn của danh sách ta chia đoạn đó thành 2 phần và ,trong đó tiến hành sắp xếp với mỗi phần rồi trộn chúng lại. Lời gọi thủ tục sắp xếp trộn với sẽ cho kết quả là sắp toàn bộ danh sách
Ví dụ: Cho danh sách
Giải thuật trộn đệ quy chia a thành hai danh sách con và tiến hành 3 bướcDanh sách trái | Danh sách phải |
2,7,6 | 3,4,5,1 |
- Sắp xếp trộn danh sách trái 2,7,6
Quá trình chia | Quá trình trộn | ||||
2,7,6 | 2,6,7 | ||||
2 | 7,6 | 2 | 6,7 | ||
2 | 7 | 6 | 2 | 7 | 6 |
- Sắp xếp trộn danh sách phải 3,4,5,1
Quá trình chia | Quá trình trộn | ||||||
3,4,5,1 | 1,3,4,5 | ||||||
3,4 | 5,1 | 3,4 | 1,5 | ||||
3 | 4 | 5 | 1 | 3 | 4 | 5 | 1 |
- Trộn danh sách trái 2,6,7 với danh sách phải 1,3,4,5
Danh sách trái | Danh sách phải | Danh sách trộn |
2,6,7 | 1,3,4,5 | 1,2,3,4,5,6,7 |
Trộn các đường tự nhiên
[sửa | sửa mã nguồn]Như trong phần đánh giá giải thuật, một trong những nhược điểm lớn của thuật toán Trộn trực tiếp là không tận dụng những thông tin về đặc tính của dãy cần sắp xếp. Ví dụ trường hợp dãy đã có thứ tự sẵn. Chính vì vậy, trong thực tế người ta ít dùng thuật toán trộn trực tiếp mà người ta dùng phiên bản cải tiến của nó. Phiên bản này thường được biết với tên gọi thuật toán trộn tự nhiên (Natural Merge sort).
Khái niệm đường chạy
[sửa | sửa mã nguồn]Để khảo sát thuật toán trộn tự nhiên, trước tiên ta cần định nghĩa khái niệm đường chạy (run):
Một đường chạy của dãy số a là một dãy con không giảm của cực đại của a. Nghĩa là, đường chạy r = (ai, ai+1,..., aj) phải thỏa điều kiện:- 0 ≤ i ≤ j < n, với n là số phần tử của dãy a
- ak ≤ ak+1 ∀k, i ≤ k ≤ j
Giải thuật
[sửa | sửa mã nguồn]Các bước thực hiện thuật toán trộn tự nhiên như sau:
- Bước 1: // Chuẩn bị
- Bước 2:
- Bước 2.1:
- Bước 2.2:
- Bước 3:
- Bước 4:
Ưu và nhược điểm
[sửa | sửa mã nguồn]Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở chỗ thay vì luôn cứng nhắc phân hoạch theo dãy con có chiều dài k, việc phân hoạch sẽ theo đơn vị là đường chạy. ta chỉ cần biết số đường chạy của a sau lần phân hoạch cuối cùng là có thể biết thời điểm dừng của thuật toán vì dãy đã có thứ tự là dãy chi có một đường chạy.
Một nhược điểm lớn nữa của thuật toán trộn là khi cài đặt thuật toán đòi hỏi thêm không gian bộ nhớ để lưu các dãy phụ b, c. Hạn chế này khó chấp nhận trong thực tế vì các dãy cần sắp xếp thường có kích thước lớn. Vì vậy thuật toán trộn thường được dùng để sắp xếp các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hoặc file.
Mã giả
[sửa | sửa mã nguồn]Mã giả ngắn gọn
[sửa | sửa mã nguồn] proceduremergesort(l,r:integer); vari,j,k,m:integer; begin ifr>lthen begin m:=(r+l)shr1; mergesort(l,m);mergesort(m+1,r); fori:=mdowntoldob[i]:=a[i]; forj:=m+1tordob[r+m+1-j]:=a[j]; fork:=ltordo ifb[i]<b[j]then begina[k]:=b[i];i:=i+1end else begina[k]:=b[j];j:=j-1end; end; end;Trộn tại chỗ
[sửa | sửa mã nguồn] Procedure Merge(k1,k2,k3:integer); Var i,j,k:integer; T: array[k1..k3] of integer; Begin i:=k1; j:=k2; k:=k3; while i<k2 and j<=k3 do Begin if a[i]<=a[j] then begin T[k]:=a[i]; i:=i+1; End else begin T[k]:=a[j]; j:=j+1; End; k:=k+1; End; if i>=k2 then while k<=k3 do begin T[k]:=a[j]; j:=j+1; k:=k+1; End if j>k3 then while k<k2 do begin T[k]:=a[i]; i:=i+1; k:=k+1; End For k:=k1 to k3 a[k]:=T[k]; EndTrộn từ dưới lên
[sửa | sửa mã nguồn] Procedure MergeSortUp (a[1..n]) Var Int m,i { m=1 while m<n { k=0 while k+m<=n { merge(a,k+1,k+m+1,Min[k+2m,n]) k=k+2m } m=2*m } }Trộn đệ quy
[sửa | sửa mã nguồn] Procedure MergeSort (k1,k2) Var k3:integer; Begin if k1<k2 then begin k3:=(k1+k2)/2; MergeSort(k1,k3); MergeSort(k3+1,k2); Merge(k1,k3,k2); End; End;Ngôn ngữ C++
void merge(int array[], int first, int middle, int last) { int temp[last + 1]; int first1, last1, first2, last2; int index = first; first1 = first; last1 = middle; first2 = middle+1; last2 = last; while((first1 <= last1) && (first2 <= last2)) { if(array[first1] < array[first2]) { temp[index] = array[first1]; index ++; first1 ++; } else { temp[index] = array[first2]; index ++; first2 ++; } } if(first2 > last2) { while(first1 <= last1) { temp[index] = array[first1]; index ++; first1 ++; } } if(first1 > last1) { while(first2 <= last2) { temp[index] = array[first2]; index ++; first2 ++; } } for(int i = first; i <= last; i ++) { array[i] = temp[i - first]; } return; } void mergeSort(int array[], int first, int last) { if(first < last) { int middle = int((first + last) / 2); mergeSort(array, first, middle); mergeSort(array, middle + 1, last); merge(array, first, middle, last); } }Xem thêm
[sửa | sửa mã nguồn]- Sắp xếp nổi bọt
- Sắp xếp chọn
- Sắp xếp chèn
- Sắp xếp nhanh
- Sắp xếp vun đống
Tham khảo
[sửa | sửa mã nguồn]- ^ Knuth (1998, tr. 158)
- ^ Jyrki Katajainen and Jesper Larsson Träff (1997). “A meticulous analysis of mergesort programs”. Chú thích journal cần |journal= (trợ giúp)
Liên kết ngoài
[sửa | sửa mã nguồn] Wikibook Algorithm implementation có một trang Merge sort- Animated Sorting Algorithms: Merge Sort – graphical demonstration and discussion of array-based merge sort
- Dictionary of Algorithms and Data Structures: Merge sort
- Mergesort applet with "level-order" recursive calls to help improve algorithm analysis
- Open Data Structures - Section 11.1.1 - Merge Sort
| ||
---|---|---|
Lý thuyết | Độ phức tạp thuật toán | Ký hiệu O lớn | Thứ tự toàn phần | Danh sách | Sắp xếp so sánh | |
Sắp xếp đổi chỗ | Sắp xếp nổi bọt | Sắp xếp cốc tai | Sắp xếp chẵn lẻ | Sắp xếp răng lược | Sắp xếp gnome | Sắp xếp nhanh | |
Sắp xếp chọn | Sắp xếp chọn | Sắp xếp vun đống | |
Sắp xếp chèn | Sắp xếp chèn | Sắp xếp Shell | Sắp xếp bằng cây | Sắp xếp thư viện | Patience sorting | |
Sắp xếp trộn | Sắp xếp trộn | Strand sort | |
Sắp xếp không so sánh | Sắp xếp theo cơ số | Sắp xếp thùng | Sắp xếp đếm | Sắp xếp chuồng bồ câu | Burstsort | Bead sort | |
Các loại khác | Sắp xếp topo | Mạng sắp xếp | Bitonic sorter | Pancake sorting | Bogosort | Stooge sort |
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
-
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
-
Thuật Toán Merge Sort(Sắp Xếp Trộn) - Poki Mobile