Cộng đồng chia sẻ tri thức Lib24.vn

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

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 11:29:17


Hợp nhất sắp xếp là một kỹ thuật sắp xếp dựa trên kỹ thuật phân chia và chinh phục. Với độ phức tạp thời gian trong trường hợp xấu nhất là Ο (n log n), đây là một trong những thuật toán được tôn trọng nhất.

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

Hợp nhất sắp xếp hoạt động như thế nào?

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

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

Chúng ta biết rằng sắp xếp hợp nhất trước tiên chia toàn bộ mảng lặp thành hai 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 gồm 8 mục được chia thành hai mảng có kích thước 4.

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

Đ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 tôi chia hai mảng này thành một nửa.

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

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

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

Bây giờ, chúng tôi kết hợp chúng theo cách chính xác giống như chúng đã bị phá vỡ. Xin lưu ý các mã màu được đưa ra cho các danh sách này.

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

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

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

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

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

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

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

Hợp nhất sắp xếp tiếp tục chia danh sách thành hai nửa bằng nhau cho đến khi không thể chia nữa. Theo định nghĩa, nếu nó chỉ là một yếu tố trong danh sách, nó đượ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ữ 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 hàm sắp xếp hợp nhất. Như 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.

Hợp nhất sắp xếp công việc với đệ quy và chúng ta sẽ thấy việc thực hiện 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

Được cập nhật: hôm kia lúc 23:54:03 | Lượt xem: 488