Giải thuật sắp xếp trộn (Merge Sort)

Giải thuật sắp xếp trộn (Merge Sort) là gì?

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.

Cách giải thuật sắp xếp trộn (Merge Sort) làm việc

Dưới đây là các hình minh họa cách giải thuật sắp xếp trộn làm việc. Giả sử chúng ta có mảng sau:

Đầu tiên, giải thuật sắp xếp trộn chia toàn bộ mảng thành hai nửa. Tiến trình chia này tiếp tục diễn ra cho đến khi không còn chia được nữa và chúng ta thu được các giá trị tương ứng biểu diễn các phần tử trong mảng. Trong hình dưới, đầu tiên chúng ta chia mảng kích cỡ 8 thành hai mảng kích cỡ 4.

Tiến trình chia này không làm thay đổi thứ tự các phần tử trong mảng ban đầu. Bây giờ chúng ta tiếp tục chia các mảng này thành 2 nửa.

Tiến hành chia tiếp cho tới khi không còn chia được nữa.

Bây giờ chúng ta tổ hợp chúng theo như đúng cách thức mà chúng được chia ra.

Đầu tiên chúng ta so sánh hai phần tử trong mỗi list và sau đó tổ hợp chúng vào trong một list khác theo cách thức đã được sắp xếp. Ví dụ, 14 và 33 là trong các vị trí đã được sắp xếp. Chúng ta so sánh 27 và 10 và trong list khác chúng ta đặt 10 ở đầu và sau đó là 27. Tương tự, chúng ta thay đổi vị trí của 19 và 35. 42 và 44 được đặt tương ứng.

Vòng lặp tiếp theo là để kết hợp từng cặp list một ở trên. Chúng ta so sánh các giá trị và sau đó hợp nhất chúng lại vào trong một list chứa 4 giá trị, và 4 giá trị này đều đã được sắp thứ tự.

Sau bước kết hợp cuối cùng, danh sách sẽ trông giống như sau:

Phần tiếp theo chúng ta tìm hiểu một số khía cạnh khác của giải thuật sắp xếp trộn.

Giải thuật cho Sắp xếp trộn (Merge Sort)

Giải thuật sắp xếp trộn tiếp tục tiến trình chia danh sách thành hai nửa cho tới khi không thể chia được nữa. Theo định nghĩa, một list mà chỉ có một phần tử thì list này coi như là đã được sắp xếp. Sau đó, giải thuật sắp xếp trộn kết hợp các sorted list lại với nhau để tạo thành một list mới mà cũng đã được sắp xếp.

Bước 1: Nếu ch có mt phn t trong list thì list này được xem như là đã được 
sp xếp. Tr v list hay giá tr nào đó.
Bước 2: Chia list mt cách đệ qui thành hai na cho ti khi không th chia được na.
Bước 3: Kết hp các list nh hơn (đã qua sp xếp) thành list mi (cũng đã được sp xếp).

Giải thuật mẫu cho Sắp xếp trộn (Merge Sort)

Có thể nói rằng với giải thuật sắp xếp trộn, bạn cần chú ý hai điểm chính: chia và hợp.

Bởi vì giải thuật sắp xếp trộn làm việc theo phương thức đệ qui nên phần triển khai giải thuật chúng ta cũng nên sử dụng đệ qui để biểu diễn.

Bt đầu gii thut sp xếp trn mergesort( biến a là mt mng )
   if ( n == 1 ) return a

   khai báo biến l1 là mt mng = a[0] ... a[n/2]
   khai báo biến l2 là mt mng = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 ) // gọi hàm merge()
Kết thúc gii thut


Bt đầu hàm merge( Mng a, mng b )

   khai báo biến c là mt mng

   while ( a và b có phn t )
      if ( a[0] > b[0] )
         Thêm b[0] vào cui mng c
         Xóa b[0] t b
      else
         Thêm a[0] vào cui mng c
         Xóa a[0] t a
 kết thúc if
   kết thúc while
   
   while ( a có phn t )
      Thêm a[0] vào cui mng c
      Xóa a[0] t a
   kết thúc while
   
   while ( b có phn t )
      Thêm b[0] vào cui mng c
      Xóa b[0] t b
   kết thúc while
   
   return c
	
Kết thúc hàm