Insertion Sort is a simple sorting algorithm that sorts a list of elements one element at a time. In simple words, Insertion sort takes a list as an input, sorts the list by changing the position of one element at a time. Insertion sort is a very simple algorithm for sorting lists but it also have its advantages.
Insertion Sort is:
- Easy to implement than other sorting algorithms
- Very efficient in sorting small size lists
- Require a constant amount of memory for the process
- Sorts a list as it receives it
- More efficient in practice than most of the sorting algorithms
Insertion sort works the same way as most people sort playing cards. Comparing the card with the other card and swapping one card at a time.
How it works?
Insertion sort takes a list of elements as an input. The algorithm will always assumes the first element as sorted and iterates over all other elements of the list one by one and checks each element with it previuos element. If the previous element is bigger than the current element it will swap them both and then again checks the previous element until the element is at the right position. It iterates over all the elements until the list is sorted.
Figure from Introduction to Algorithms by MIT Press
Implementation
Here's a simple implementation of insertion sort in Python.
nums = [4, 7, 3, 1, 5, 8, 0, 6, 9, 2]
i = 1
while i < len(nums):
j = i
""" Iterates j times to check if the element
is at the right position """
while j > 0 and nums[j-1] > nums[j]:
nums[j], nums[j-1] = nums[j-1], nums[j] # element swapping
j = j-1
i = i+1
print(nums) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Complesity
The Complexity of Insertion Sort in Best, Worst and Average Case is as follows.
In Best Case
Considering that the provided list is already sorted, Insertion sort will have complexity of O(n) or Linear Complexity. It will only check for one element on each iteration and will takes n steps to sort the list if the lenght of list is n.
In Worst Case
Considering that the provided list is already sorted in the reverse order, Insertion sort will have the complexity of O(n^2) or Quadratic Complexity. It will iterate over all the elements one by one and swap evey element that comes before the current element until the list is completely sorted.
list = [9, 8, 7, 6, 5, 4, 3, 2, 1]
0- [9, 8, 7, 6, 5, 4, 3, 2, 1]
1- [8, 9, 7, 6, 5, 4, 3, 2, 1]
2- [8, 7, 9, 6, 5, 4, 3, 2, 1]
3- [7, 8, 9, 6, 5, 4, 3, 2, 1]
4- [7, 8, 6, 9, 5, 4, 3, 2, 1]
...
...
37- [1, 2, 3, 4, 5, 6, 7, 8, 9]
The bigger the list more time and steps it will take to sort an unordered list with insertion sort.
In Average Case
The same goes for Average Case with insertion as was with Worst Case having the time complexity of O(n^2).
Insertion sort was easy and simple one but I don't think next ones will be as simple, So let's see what will happen.
zainsci