Giải thích Sắp xếp Hợp nhất trong Python

Sắp xếp hợp nhất là một kỹ thuật sắp xếp. Đây là một thuật toán sắp xếp hiệu quả với độ phức tạp về thời gian là ( n logn ) trong đó n là độ dài của mảng được sắp xếp.

Sắp xếp hợp nhất là một thuật toán tuân theo mô hình Chia và Conquers. Nó liên tục chia mảng thành hai nửa bằng nhau. Sau đó, nó bắt đầu sắp xếp các danh sách có mỗi phần tử duy nhất và liên tục hợp nhất các danh sách đã sắp xếp để tạo thành danh sách được sắp xếp hoàn chỉnh.

Do đó, chúng tôi thu được một mảng được sắp xếp.

Ví dụ

Các hộp màu tím và mũi tên màu đen hiển thị việc chia danh sách thành hai nửa.

Các hộp màu xanh lục và mũi tên màu đỏ hiển thị sự hợp nhất của hai danh sách đã sắp xếp.

Triển khai Sắp xếp Hợp nhất

Việc chia danh sách thành hai nửa khá dễ dàng và nó được thực hiện một cách đệ quy cho đến khi chúng ta chỉ còn lại một phần tử. Sau đó, thủ tục hợp nhất được thực hiện, đây thực sự là nơi chúng tôi áp dụng logic của việc hợp nhất hai danh sách được sắp xếp lại với nhau.

Ví dụ

Hàm hợp nhất nhận hai mảng đã sắp xếp để được hợp nhất. Phần tử đứng nhất của a1 được so sánh với phần tử đứng trước nhất của a2. Phần nhỏ nhất trong hai phần được thêm vào danh sách c và con trỏ của mảng đó được tăng dần.

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

Đầu ra

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]