Trong bài viết này, chúng ta sẽ tìm hiểu về giải pháp cho câu hỏi được đưa ra bên dưới.
Tuyên bố sự cố - Chúng ta được cung cấp một mảng, chúng ta cần sắp xếp nó bằng cách sử dụng khái niệm sắp xếp chèn nhị phân.
Ở đây như tên gợi ý, chúng tôi sử dụng khái niệm tìm kiếm nhị phân cùng với thuật toán sắp xếp chèn.
Bây giờ chúng ta hãy quan sát giải pháp trong việc triển khai bên dưới -
Ví dụ
# sort
def insertion_sort(arr):
for i in range(1, len(arr)):
temp = arr[i]
pos = binary_search(arr, temp, 0, i) + 1
for k in range(i, pos, -1):
arr[k] = arr[k - 1]
arr[pos] = temp
def binary_search(arr, key, start, end):
#key
if end - start <= 1:
if key < arr[start]:
return start - 1
else:
return start
mid = (start + end)//2
if arr[mid] < key:
return binary_search(arr, key, mid, end)
elif arr[mid] > key:
return binary_search(arr, key, start, mid)
else:
return mid
# main
arr = [1,5,3,4,8,6,3,4]
n = len(arr)
insertion_sort(arr)
print("Sorted array is:")
for i in range(n):
print(arr[i],end=" ") Đầu ra
Sorted array is : 1 3 3 4 4 5 5 6 8
Tất cả các biến được khai báo trong phạm vi cục bộ và các tham chiếu của chúng được hiển thị trong hình trên.
Kết luận
Trong bài viết này, chúng ta đã tìm hiểu về cách chúng ta có thể tạo một Chương trình Python cho Phân loại Chèn nhị phân