Chương trình Python để sắp xếp chèn

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

Thuật toán

1. Iterate over the input elements by growing the sorted array at each iteration.
2. Compare the current element with the largest value available in the sorted array.
3. If the current element is greater, then it leaves the element in its place 
   and moves on to the next element else it finds its correct position in the 
   sorted array and moves it to that position in the array.
4. This is achieved by shifting all the elements towards the right, which are 
   larger than the current element, in the sorted array to one position ahead.

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.