**Insertion sort implemented in python:**

In the python code below we have a list containing 10 unsorted numbers to sort. In the first while loop we are iterating from the 2nd element so that the first element of the list becomes the first element of the sorted list. The first while loop selects an element from the unsorted list and the second while loop (nested inside first one) compares it with elements of the sorted list, if the selected element is less than the adjacent left element (sorted portion) then the left element is shifted into the current element's place and the current element is copied into the left element's place. The last while loop finally displays the sorted list.

list=[10,1,5,0,6,8,7,3,11,4] i=1 while(i<10): element=list[i] j=i i=i+1 while(j>0 and list[j-1]>element): list[j]=list[j-1] j=j-1 list[j]=element i=0 while(i<10): print (list[i]) i=i+1

**Time complexity: O(n²)**

watch this video for understanding the algorithm, its implementation and time complexity.

Tweet

## No comments:

## Post a Comment