How to perform Insertion Sort in Python ?
By Aayush GuptaIn this tutorial, we will learn the procedure of sorting an unsorted list using the pre-defined algorithm of Insertion Sort in Python.
Also, have a look at other sorting methods :
Insertion Sort in Python
It is a sorting method which works on picking one element at a time from an unsorted list and then placing it accordingly at its correct position.
ADVANTAGES Of Insertion Sort:
- Simple Implementation as compared to other complex methods.
- Efficient that other O(n2) methods like Selection sort and Bubble sort.
- Requires a constant amount of space irrespective of size of list O(1).
- A stable sorting method.
However, this method is comparatively slow for large data sets as compared to other methods like Quick sort, Merge sort and Heap sort.
Implementing Insertion Sort
data_list=list(map(int, input().split()))
for i in range(1,len(data_list)):
temp=data_list[i]
j=i-1
while(j>=0 and data_list[j]>temp):
data_list[j+1]=data_list[j]
j=j-1
data_list[j+1]=temp
print(data_list)
Input :
323 2 12 1 4 54 5 3
Output :
[1, 2, 3, 4, 5, 12, 54, 323]
Explanation :
Insertion Sort selects the element of right of what was already sorted. Then slide up each larger element until it gets to the correct position.
Consider the following unsorted array :
70 49 31 6 65 15 51
Step 1 : Element 70 is compared with 49 and swapped
49 70 31 6 65 15 51
Step 2 : Element 31 compared with 70 and swapped
49 31 70 6 65 15 51
Step 3 : Further 31 is also swapped with 49 as 31<49
31 49 70 6 65 15 51
Step 4 : Then element 6, is swapped with 70, then 49, and then 31
6 31 49 70 65 15 51
Step 5 :65 swapped with 70
6 31 49 65 70 15 51
Step 6 : 15 swapped with 70, then 65, then 49, then finally 31
6 15 31 49 65 70 51
Step 7 : 51 is swapped by 70, and then by 65
6 15 31 49 51 65 70
Insertion sort also breaks the whole list into two sections- Sorted and Unsorted. Then with every iteration, it takes elements from the unsorted list and adds them up to the sorted section at appropriate position.
That’s it! Hope you get well versed with the concept of Insertion Sort.
Drop any queries you face in the comments section below.
Also, have a look at :
Leave a Reply