Cấu trúc dữ liệu - Thuật toán sắp xếp hợp nhất

Merge sort là một kỹ thuật sắp xếp dựa trên kỹ thuật chia để trị. Với độ phức tạp thời gian trong trường hợp xấu nhất là Ο (n log n), nó là một trong những thuật toán được đánh giá cao nhất.

Sắp xếp hợp nhất trước tiên chia mảng thành các nửa bằng nhau và sau đó kết hợp chúng theo cách đã sắp xếp.

Cách Merge Sort hoạt động?

Để hiểu sắp xếp hợp nhất, chúng tôi lấy một mảng không được sắp xếp như sau:

Chúng ta biết rằng sắp xếp hợp nhất chia lặp lại toàn bộ mảng thành các nửa bằng nhau trừ khi đạt được các giá trị nguyên tử. Ở đây chúng ta thấy rằng một mảng 8 mục được chia thành hai mảng có kích thước 4.

Điều này không thay đổi trình tự xuất hiện của các mục trong bản gốc. Bây giờ chúng ta chia hai mảng này thành một nửa.

Chúng tôi tiếp tục chia các mảng này và chúng tôi đạt được giá trị nguyên tử mà không thể chia được nữa.

Bây giờ, chúng tôi kết hợp chúng theo cách giống hệt như khi chúng được chia nhỏ. Vui lòng lưu ý các mã màu được cung cấp cho các danh sách này.

Trước tiên, chúng tôi so sánh phần tử cho từng danh sách và sau đó kết hợp chúng thành một danh sách khác theo cách được sắp xếp. Chúng ta thấy rằng 14 và 33 ở các vị trí đã được sắp xếp. Chúng tôi so sánh 27 và 10 và trong danh sách mục tiêu có 2 giá trị, chúng tôi đặt 10 đầu tiên, tiếp theo là 27. Chúng tôi thay đổi thứ tự của 19 và 35 trong khi 42 và 44 được đặt tuần tự.

Trong lần lặp tiếp theo của giai đoạn kết hợp, chúng tôi so sánh danh sách của hai giá trị dữ liệu và hợp nhất chúng thành danh sách các giá trị dữ liệu tìm thấy, đặt tất cả theo thứ tự đã sắp xếp.

Sau lần hợp nhất cuối cùng, danh sách sẽ như thế này -

Bây giờ chúng ta nên tìm hiểu một số khía cạnh lập trình của sắp xếp hợp nhất.

Thuật toán

Sắp xếp hợp nhất tiếp tục chia danh sách thành các nửa bằng nhau cho đến khi không thể chia được nữa. Theo định nghĩa, nếu nó chỉ là một phần tử trong danh sách, nó sẽ được sắp xếp. Sau đó, sắp xếp hợp nhất kết hợp các danh sách được sắp xếp nhỏ hơn giữ cho danh sách mới cũng được sắp xếp.

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Mã giả

Bây giờ chúng ta sẽ thấy các mã giả cho các chức năng sắp xếp hợp nhất. Như các thuật toán của chúng tôi chỉ ra hai chức năng chính - phân chia và hợp nhất.

Merge sort hoạt động với đệ quy và chúng ta sẽ thấy việc triển khai của chúng ta theo cùng một cách.

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

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

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
	
end procedure

Để biết về triển khai sắp xếp hợp nhất trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .