Sắp xếp chèn trong Python là gì?

Sắp xếp chèn là phương pháp đơn giản để sắp xếp một mảng. Trong kỹ thuật này, mảng hầu như được chia thành phần được sắp xếp và phần chưa được sắp xếp. Một phần tử từ phần chưa được sắp xếp sẽ được chọn và được đặt ở vị trí chính xác trong phần được sắp xếp.

• Các phần tử của mảng được chuyển từ 1 đến n.

• Nếu phần tử mảng ở vị trí i lớn hơn phần tử trước của nó, nó không cần phải di chuyển.

• Nếu phần tử mảng ở vị trí i nhỏ hơn phần tử trước của nó, thì phần tử đó cần được dịch chuyển sang trái cho đến khi chúng tôi tìm thấy phần tử trước nhỏ hơn nó hoặc nếu chúng tôi đạt đến vị trí ngoài cùng bên trái trong mảng.

Ví dụ

Chúng ta có thể hiểu ý tưởng trên rõ ràng hơn với sự trợ giúp của một ví dụ. Giả sử chúng ta có mảng sau -

Chúng ta cần bắt đầu duyệt qua mảng từ chỉ mục 1 (vì chỉ mục 0 không có tiền nhiệm).

Ở chỉ mục 1 -

6 lớn hơn so với người tiền nhiệm của nó, do đó không cần phải làm gì.

Ở chỉ mục 2 -

1 thấp hơn so với người tiền nhiệm của nó, do đó chúng ta cần phải di chuyển nó sang bên trái trừ khi chúng ta tìm thấy người tiền nhiệm nhỏ hơn nó hoặc nếu chúng ta đạt chỉ số 0. Trong trường hợp này, chúng ta sẽ đạt chỉ số 0.

Ở chỉ mục 3 -

Ở chỉ mục 4 -

Dịch chuyển 2 sang trái, cho đến khi chúng tôi tìm thấy giá trị trước nhỏ hơn 2.

Ở chỉ mục 5 -

Dịch chuyển 5 sang trái, cho đến khi chúng tôi tìm thấy giá trị tiền nhiệm nhỏ hơn 5.

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

Sắp xếp chèn là một thuật toán sắp xếp tại chỗ với độ phức tạp thời gian O (n ^ 2) và độ phức tạp không gian O (1).

Ví dụ

def insertionSort(arr):
   for i in range(1, len(arr)):
      key = arr[i] #get each element
      j = i-1
      while j >= 0 and key &lit; arr[j] : #keep shifting until reaching index 0 or getting an element smaller than key
         arr[j + 1] = arr[j]
         j=j-1
      arr[j + 1] = key

arr = [4,6,1,7,2,5]
insertionSort(arr)
for i in range(len(arr)):
   print (arr[i],end=" ")

Đầu ra

1 2 4 5 6 7