Insertion Sort in Python

Insertion Sort in Python

Insertion Sort in Python

Insertion sort examine the previously sorted sub-array and insert an element at its proper position.
If you have an array a[0], a[1], a[2], a[3],……….a[n].
Then in insertion sort a[0] trivially sorted sub-array.
Again compare a[0] to a[1] and if a[0]> a[1] exchange it.
Now sub-array a[0],a[1] is sorted again compare a[2] with sub-array a[0],a[1] and insert it into proper position.
Now sub-array a[0],a[1],[2] is sorted again compare a[3] with sub-array a[0],a[1],[2] and insert it into proper position.
This process will go on until array a[] is sorted.

See a numerical example, then your understanding will be more clear.

Insertion Sort in Python

Insertion Sort in PythonInsertion Sort in Python

Insertion Sort in PythonInsertion Sort in PythonInsertion Sort in PythonInsertion Sort in PythonInsertion Sort in PythonInsertion Sort in Python

Insertion Sort in Python


a=[15, 23, 40, 10, 3, 35, 25, 5, 30, 33]
for i in range(len(a)):
        t=a[i]
        j=i-1
        while t < a[j] and j >= 0:
              a[j+1]=a[j]
               j=j-1
       a[j+1]=t
print(a)


Time complexity of Insertion Sort

The average and worst case complexities of insertion sort is O(n2), and best case complexity is O(n).

Leave a Comment

Your email address will not be published. Required fields are marked *

©Postnetwork-All rights reserved.