Sắp xếp chèn trong chương trình Python

Trong bài viết này, chúng ta sẽ tìm hiểu về cách triển khai Insertion sort trong Python 3.x. Hoặc sớm hơn.

Thuật toán

• Lặp lại các phần tử đầu vào bằng cách tăng mảng đã sắp xếp ở mỗi lần lặp.

• So sánh phần tử hiện tại với giá trị lớn nhất có sẵn trong mảng đã sắp xếp.

• Nếu phần tử hiện tại lớn hơn, thì phần tử đó sẽ giữ nguyên vị trí của nó và chuyển sang phần tử tiếp theo khác, phần tử đó sẽ tìm vị trí chính xác của nó trong mảng đã sắp xếp và di chuyển nó đến vị trí đó trong mảng.

• Điều này đạt được bằng cách dịch chuyển tất cả các phần tử về phía bên phải, lớn hơn phần tử hiện tại, trong mảng đã sắp xếp về phía trước một vị trí.

Bây giờ chúng ta hãy xem phần trình bày trực quan của thuật toán

Bây giờ chúng ta hãy xem việc triển khai

Ví dụ

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i]
      # Move elements of arr[0..i-1], that are greater
      than key,
      # to one position ahead of their current position
      j = i-1
      while j >=0 and key < arr[j] :
         arr[j+1] = arr[j]
         j -= 1
      arr[j+1] = key
# main
arr = ['t','u','t','o','r','i','a','l']
insertionSort(arr)
print ("The sorted array is:")
for i in range(len(arr)):
   print (arr[i])

Đầu ra

The sorted array is:
a
i
l
o
r
t
t
u

Độ phức tạp về thời gian: O (n * 2)

Không gian phụ trợ: O (1)

Tất cả các biến được khai báo trong khung toàn cục như thể hiện trong hình bên dưới -

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về loại Chèn và cách triển khai của nó trong Python 3.x. hoặc sớm hơn.