Sắp xếp trộn

Bách khoa toàn thư mở Wikipedia

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 đó. 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ị. Nó được xếp vào thể loại sắp xếp so sánh.

Mục lục 1 Trộn 2 Trộn tại chỗ 3 Trộn từ dưới lên 4 Sắp xếp trộn đệ quy 5 Giả mã 5.1 Trộn 5.2 Trộn từ dưới lên 5.3 Trộn đệ quy

[sửa] Trộn

Giả sử có hai danh sách đã được sắp xếp a[1..m] và 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.

Ví dụ: Cho hai danh sách a = (1,3,7,9),b = (2,6), 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

[sửa] Trộn tại chỗ

Giả sử trong danh sách a[1..n] có 2 danh sách con kề nhau a[k₁..k₂] và a[k₂ + 1..k₃] đã đượ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 T[k₁..k₃] 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ỗ.

[sửa] Trộn từ dưới lê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 a ta trộn a[1] với a[2], a[3] với a[4],... Khi đó mọi danh sách con gồm hai phần tử của 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 a = (2,3,5,6,4,1,7)

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ửa] Sắp xếp trộn đệ quy

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 a[k₁..k₂] của danh sách a[1..n] ta chia đoạn đó thành 2 phần a[k₁..k₃] và a[k₃ + 1..k₂],trong đó k₃ = int((k₁ + k₂) / 2) 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 a[1..n] sẽ cho kết quả là sắp toàn bộ danh sách a[1..n]

Ví dụ: Cho danh sách a = [2,7,6,3,4,5,1]

Giải thuật trộn đệ quy chia a thành hai danh sách con và tiến hành 3 bước

Danh 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	6	7

• • 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

[sửa] Giả mã

[sửa] Trộn

Procedure Merge(a,k1,k2,k3)
 Var Int i,j,k
           List  T[k1..k3]  
{
   i=k1
   j=k2
   k=k1
  while i<=k1 and j<=k3
   {
     if a[i]<=a[j] then  {
         T[k]=a[i]
         i=i+1
       }
       else {
         T[k]=a[j]
         j=j+1
       }
    k=k+1
   }
   if i>k1 then
        while k<=k3 {
           T(k)=a[j]
           j=j+1
           k=k+1
       {
   if j>k3 then
        while k<=k2 {
           T(k)=a[i]
           i=i+1
           k=k+1
       {
    For k=k1 to k3
          a[k]=T[k]
}

[sửa] Trộn từ dưới lê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,k+2m)
    k=k+2m
   }
   }
  m=2*m
  }

[sửa] Trộn đệ quy

Procedure MergeSort (a,k1,k2)
 Var Int k3
 {If k1<k2 then {
  k3=int((k1+k2)/2)
  MergeSort(a,k1,k3)
  MergeSort(a,k3+1,k2)
  Merge(k1,k2,k3)
 }
 }