Sắp Xếp Trộn(Merge Sort)

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.

1.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

2.Trộn tại chỗ

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

3.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

4.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[k1..k2] của danh sách a[1..n] ta chia đoạn đó thành 2 phần a[k1..k3] và a[k3 + 1..k2],trong đó k3 = int((k1 + k2) / 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 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

5.Trộn các đường tự nhiê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).

5.1.Khái niệm đường chạy

Ðể 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

Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 có thể coi như gồm 5 đường chạy (12); (2, 8); (5); (1, 6); (4, 15).

5.2.Giải thuật

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ị

r = 0; // r dùng để đếm số dường chạy

  • Bước 2 :

Tách dãy a1, a2, …, an thành 2 dãy b, c theo nguyên tắc luân phiên từng đường chạy:

  • Bước 2.1 :

Phân phối cho b một đường chạy; r = r+1;

Nếu a còn phần tử chưa phân phối

Phân phối cho c một đường chạy; r = r+1;

  • Bước 2.2 :

Nếu a còn phần tử: quay lại bước 2.1;

  • Bước 3 :

Trộn từng cặp đường chạy của 2 dãy b, c vào a.

  • Bước 4 :

Nếu r <= 2 thì trở lại bước 2;

Ngược lại: Dừng;

5.3.Ưu và nhược điểm

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

6.Giải thuật

6.1.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<k2 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>=k2 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]
}

6.2.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+1,k+2m)
       k=k+2m
     }
   }
   m=2*m
 }

6.3.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(a,k1,k3+1,k2)
     }
 }

7.Cài đặt bằng Java

7.1.Lớp MergeSort

 
 1  // Figure 16.10: MergeSort.java
 2  // Class that creates an array filled with random integers.
 3  // Provides a method to sort the array with merge sort.
 4  import java.util.Random;
 5
 6  public class MergeSort
 7  {
 8     private int [] data; // array of values
 9     private static Random generator = new Random();
10
11     // create array of given size and fill with random integers
12     public MergeSort( int size )
13     {
14        data = new int [ size ]; // create space for array
15
16        // fill array with random ints in range 10-99
17        for ( int i = 0 ; i < size; i++ )
18           data[ i ] = 10 + generator.nextInt( 90 );
19     } // end MergeSort constructor
20
21       // calls recursive split method to begin merge sorting
22       public void sort()                                    
23       {
24          sortArray( 0, data.length - 1 ); // split entire array
25       } // end method sort                                 
26 
27       // splits array, sorts subarrays and merges subarrays into sorted array
28       private void sortArray( int low, int high )                            
29       {
30          // test base case; size of array equals 1     
31          if ( ( high - low ) >= 1 ) // if not base case
32          {
33             int middle1 = ( low + high ) / 2; // calculate middle of array
34             int middle2 = middle1 + 1; // calculate next element over     
35 
36             // output split step
37             System.out.println( "split:   " + subarray( low, high ) );
38             System.out.println( "         " + subarray( low, middle1 );
39             System.out.println( "         " + subarray( middle2, high ) );
40             System.out.println();
41 
42             // split array in half; sort each half (recursive calls)
43             sortArray( low, middle1 ); // first half of array       
44             sortArray( middle2, high ); // second half of array     
45 
46             // merge two sorted arrays after split calls return
47             merge ( low, middle1, middle2, high );             
48          } // end if                                           
49       } // end method split                                    
50 
51       // merge two sorted subarrays into one sorted subarray             
52       private void merge( int left, int middle1, int middle2, int right )
53       {
54          int leftIndex = left; // index into left subarray              
55          int rightIndex = middle2; // index into right subarray         
56          int combinedIndex = left; // index into temporary working array
57          int [] combined = new int [ data.length ]; // working array    
58 
59          // output two subarrays before merging
60          System.out.println( "merge:   " + subarray( left, middle1 ) );
61          System.out.println( "         " + subarray( middle2, right ) );
62 
63          // merge arrays until reaching end of either         
64          while ( leftIndex <= middle1 && rightIndex <= right )
65          {
66             // place smaller of two current elements into result  
67             // and move to next space in arrays                   
68             if ( data[ leftIndex ] <= data[ rightIndex ] )        
69                combined[ combinedIndex++ ] = data[ leftIndex++ ]; 
70             else                                                  
71                combined[ combinedIndex++ ] = data[ rightIndex++ ];
72          } // end while                                           
73 
74          // if left array is empty                                
75          if ( leftIndex == middle2 )                              
76             // copy in rest of right array                        
77             while ( rightIndex <= right )                         
78                combined[ combinedIndex++ ] = data[ rightIndex++ ];
79          else // right array is empty                             
80             // copy in rest of left array                         
81             while ( leftIndex <= middle1 )                        
82                combined[ combinedIndex++ ] = data[ leftIndex++ ]; 
83 
84          // copy values back into original array
85          for ( int i = left; i <= right; i++ )  
86             data[ i ] = combined[ i ];          
87 
88          // output merged array
89          System.out.println( "        " + subarray( left, right ) );
90          System.out.println();
91       } // end method merge
92 
93       // method to output certain values in array
94       public String subarray( int low, int high )
95       {
96          StringBuffer temporary = new StringBuffer();
97 
98          // output spaces for alignment
99          for ( int i = 0; i < low; i++ )
100            temporary.append( "   " );
101 
102         // output elements left in array
103         for ( int i = low; i <= high; i++ )
104            temporary.append( " " + data[ i ] );
105 
106         return temporary.toString();
107      } // end method subarray
108 
109      // method to output values in array
110      public String toString()
111      {
112         return subarray( 0, data.length - 1 );
113      } // end method toString
114   } // end class MergeSort

7.2.Lớp MergeShortTest

1  // Figure 16.11: MergeSortTest.java

2  // Test the merge sort class.

3

4  public class MergeSortTest

5  {

6     public static void main( String[] args )

7     {

8        // create object to perform merge sort

9        MergeSort sortArray = new MergeSort( 10 );

10

11        // print unsorted array

12        System.out.println( “Unsorted:” + sortArray + “\n” );

13

14        sortArray.sort(); // sort array

15

16        // print sorted array

17        System.out.println( “Sorted:  ” + sortArray );

18     } // end main

19  } // end class MergeSortTest

Kết quả

Unsorted: 75 56 85 90 49 26 12 48 40 47

split:    75 56 85 90 49 26 12 48 40 47

75 56 85 90 49

26 12 48 40 47

split:    75 56 85 90 49

75 56 85

90 49

split:    75 56 85

75 56

85

split:    75 56

75

56

merge:    75

56

56 75

merge:    56 75

85

56 75 85

split:            90 49

90

49

merge:            90

49

49 90

merge:    56 75 85

49 90

49 56 75 85 90

split:                   26 12 48 40 47

26 12 48

40 47

split:                   26 12 48

26 12

48

split:                   26 12

26

12

merge:                   26

12

12 26

merge:                   12 26

48

12 26 48

split:                            40 47

40

47

merge:                            40

47

40 47

merge:                   12 26 48

40 47

12 26 40 47 48

merge:    49 56 75 85 90

12 26 40 47 48 49 56 75 85 90

Sorted:   12 26 40 47 48 49 56 75 85 90

Các bài liên quan:
Thuật toán sắp xếp – Phần 3