Do you remember how you arrange your hand of cards in childhood? You first pick one card, then pick the next card and put it after the first card if it is bigger or before the first card if it is smaller. then you pick another card and insert it into its proper position. This is one of the most common examples of an insertion sort. You can easily implement insertion sort in python because python comes with a host of different functions each built specifically to add more versatility to the interface than before.
The Insertion sort in Python is another simple sorting algorithm, which can be used to sort any linear data structure like a list or linked list. On simplicity, this is next to bubble sort, and it’s also pretty close to how humans manually sort something (for example, a hand of playing cards). As the name suggests, Insertion sort is based upon insertion of an element in a sorted list.
What is Insertion Sort in Python: Overview
In the insertion sort technique, we start from the second element. Then compare it with the first element and put it in a proper place. Then we perform this process for the subsequent elements.
You can easily understand how insertion sort works in Python with the GIF shown below.
We compare each element with all its previous elements and put or insert the element in its proper position. Insertion sort technique is more feasible for lists with a smaller number of elements. It is also useful for sorting linked lists in Python.
Working of Insertion Sort in Python
To understand Insertion sort in Python we have taken an unsorted list for our example.
Insertion sort compares the first two elements.
It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.
Insertion sort moves ahead and compares 33 with 27.
And finds that 33 is not in the correct position.
It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.
These values are not in sorted order.
So we swap the elements of the list.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We swap them again. By the end of the third iteration, we have a sorted sub-list of 4 items.
This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see some programming aspects of insertion sort.
So in conclusion how insertion sort works in Python we can say, it compares the current element with the elements on the left-hand side (sorted list). If the current element is greater than all the elements on its left-hand side, then it leaves the element in its place and moves on to the next element. Else it finds its correct position and moves it to that position by shifting all the elements, which are larger than the current element, in the sorted list to one position ahead.
Algorithm For Python Insertion Sort
- If the element is the first one, it is already sorted.
- Move to the next element of the list.
- Compare the current element with all elements in the sorted list.
- If the element in the sorted list is smaller than the current element, iterate to the next element. Otherwise, shift all the greater element in the list by one position towards the right.
- Insert the value at the correct position.
- Repeat until the complete list is sorted.
Pseudocode
Following is the pseudocode of Insertion Sort for a zero-indexed list:
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end whileImplementation of Insertion sort
Implementation of Insertion Sort algorithm in Python Programming language.
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+1Output:
0
1
3
4
5
6
7
8
10
11Explanation:
In the above python code, 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.
Complexity Analysis
From the pseudo code and the illustration above, insertion sort is the efficient algorithm when compared to bubble sort or selection sort. Instead of using for loop and present conditions, it uses a while loop that does not perform any more extra steps when the list is sorted.
However, even if we pass the sorted list to the Insertion sort technique, it will still execute the outer for loop thereby requiring n number of steps to sort an already sorted list. This makes the best time complexity of insertion sort a linear function of N where N is the number of elements in the list.
Thus the various complexities for Insertion sort technique are given below:
| Worst-case time complexity | O(n2) |
| Best case time complexity | O(n) |
| Average time complexity | O(n2) |
| Space complexity | O(1) |
In spite of these complexities, we can still conclude that Insertion sort is the most efficient algorithm when compared with the other sorting techniques like Bubble sort and Selection sort.
Characteristics of Insertion sort
- Insertion sort takes maximum time for execution in the worst-case scenario where the given input elements are sorted in reverse order. It takes the least time in its best-case scenario where the elements are already sorted.
- Insertion sort follows an incremental approach in achieving its results.
- It is well preferred when the number of elements is less in number and most of the elements are in a sorted manner.
- The complexity involved in insertion sort can be reduced to O(log n) if the binary search method is adopted to search its sorted list each time to place an element from the unsorted number appropriately. This process can be referred to as Binary Insertion Sort.
Notes
- Due to its costly time complexity for copy operations, insertion sort is not typically used to sort a list.
- Insertion sort in Python is an efficient way to insert a limited number of items into an already sorted list.
- This algorithm technique is more efficient than the Bubble sort and Selection sort techniques.
- Insertion sort in Python is less efficient than the other techniques like Quicksort and Merge sort.
Real-World Example of Insertion Sort
When we are playing cards each time we take a new card and insert at its proper position that’s the logic of insertion sort.
One more real-world example of insertion sort is how tailors arrange shirts in a cupboard, they always keep them in sorted order of size and thus insert new shirt at the right position very quickly by moving other shirts forward to keep the right place for a new shirt.
Must Read
How to Convert String to Lowercase in Python
How to Calculate Square Root in Python
Python User Input | Python Input () Function | Keyboard Input
Best Book to Learn Python in 2020
Python Reverse List Using reverse() reversed() and Slicing
Conclusion
Indeed, it’s not as good as quicksort, heap sort, or mergesort for sorting large lists, but it’s good enough to sort small integer lists where the cost of comparison is small.
Insertion Sort Python is a very simple, generally inefficient algorithm that nonetheless has several specific advantages that make it relevant even after many other, generally more efficient algorithms have been developed.
It remains a great algorithm for introducing future software developers into the world of sorting algorithms and is still used in practice for specific scenarios in which it shines.
Happy Coding!