To learn about Insertion Sort, you must know:
- Python 3
- Python data structures - Lists
What is Insertion Sort?
We are in the second tutorial of the sorting series. The previous tutorial talks about Bubble Sort which is a very simple sorting algorithm. If you haven’t read that, you can find it here. Like all sorting algorithms, we consider a list to be sorted only if it is in the ascending order. Descending order is considered the worst unsorted case.
As the name suggests, in Insertion Sort, an element gets compared and inserted into the correct position in the list. To apply this sort, you must consider one part of the list to be sorted and the other to be unsorted. To begin, consider the first element to be the sorted portion and the other elements of the list to be unsorted. Now compare each element from the unsorted portion with the element/s in the sorted portion. Then insert it in the correct position in the sorted part. Remember, the sorted portion of the list remain sorted at all times.
Let us see this using an example, alist = [5,9,1,2,0]
sorted - 5 and unsorted - 9,1,2,0 5<9: nothing happens alist = [5,9,1,2,0]
sorted - 5, 9 and unsorted - 1,2,0 1<9: do nothing 1<5: insert 1 before 5 alist = [1,5,9,2,7,0]
sorted -1, 5, 9 and unsorted - 2,0 2<9: do nothing 2<5: do nothing 2>1: do nothing insert 2 before 5 alist = [1,2,5,9,0]
Note: even though it is clear for us that 2 is lesser than 5 but greater than 1, the algorithm has no way of knowing this. Hence only after comparing with all the elements in the sorted part, it makes the insertion is the correct place.
sorted -1, 2, 5, 9 and unsorted - 0 0<9: do nothing 0<5: do nothing 0<2: do nothing 0<1: insert 0 before 1 alist = [0,1,2,5,9]
See this animation for better understanding.
How to implement Insertion Sort?
Now that you have a fair understanding of what Insertion Sort is, let us take a look at the algorithm and its code.
- Consider the first element to be sorted and the rest to be unsorted
- Compare with the second element:
- If the second element< the first element, insert the element in the correct position of the sorted portion
- Else, leave it as it is
- Repeat 1 and 2 until all elements are sorted
NOTE: As the number elements in the sorted portion increases, the new element from the unsorted portion must be compared with all the elements in the sorted list before insertion.
def insertionSort(alist): for i in range(1,len(alist)): #element to be compared current = alist[i] #comparing the current element with the sorted portion and swapping while i>0 and alist[i-1]>current: alist[i] = alist[i-1] i = i-1 alist[i] = current #print(alist) return alist print(insertionSort([5,2,1,9,0,4,6]))
Uncomment the print statement to see how the list gets sorted.
Insertion Sort works best with small number of elements. The worst case runtime complexity of Insertion Sort is o(n2) similar to that of Bubble Sort. However, Insertion Sort is considered better than Bubble sort. Explore why and comment below. That’s it for this tutorial. Happy Pythoning!