Understand the algorithm
Insertion sort is an awesome algorithm that has some quite interesting use-cases due to it nature.
First understand the basics of it.
Consider the list of integers.
The above list has 10 elements. Now if you only consider the list of the first element (number 3), then that part is actually sorted. If number 3 was the only number in the list, then it would be sorted.
Now consider the list of the first two elements.
Then we have the list of two elements, 3 and 5. Here we are lucky, as this is still sorted.
Now for the next element, 1, we are a bit out of luck, because if we just added that element to part of the list (the green part), then it would not be sorted.
If one was added, we would need to swap it down until it is on place. First swapping 1 with 5.
Then swapping 1 with 3. Then we are having a ordered list again, that is a list of the 3 first elements (the green part of the list below).
Hence, the process is to think of the first element as a list and realize it is ordered. Then insert one element at the time. For each element inserted, swap it down until it is on place.
Why is Insertion Sort great to know?
Well, first of all it is simple to understand. Second of all, it is easy to implement (see the code below). But that is not the exiting stuff.
Well, what is it?
It has some interesting use case. See.
- If you were to keep an ordered list in memory as part of your program.
- But it also had a twist.
- Someone would keep coming with new numbers all the time, and still ask you to keep the list ordered.
- Then the efficiency of keeping this list ordered is good.
Because if the list is ordered and you need to add another element, you just follow the above procedure.
The worst case run-time for a list of N element is O(N).
What is the catch?
Well, the performance of the algorithm is not good. That is, there are more efficient algorithms out there to sort N elements.
For the first element you use 1 operation. The second element 2 operations. The third element 3 operations. Wait a minute, isn’t that this formula?
1 + 2 + 3 + 4 + … + N = N(N+1)/2
Which unfortunately gives a performance of O(N^2).
So why bother about this algorithm?
Well, because of the use-case explained above. That you can keep it ordered and with low cost insert an element into it.
import random def generate_random_list(n): # n is the length of the list my_list =  for i in range(n): my_list.append(random.randint(0, 4*n)) return my_list def insertion_sort(my_list): for i in range(1, len(my_list)): for j in range(i, 0, -1): if my_list[j] < my_list[j-1]: my_list[j], my_list[j-1] = my_list[j-1], my_list[j] else: break def main(): my_list = generate_random_list(20) print(my_list) insertion_sort(my_list) print(my_list) if __name__ == "__main__": main()
The above code implements the algorithm (see only 7 lines of code) and tests it.
I hope you enjoyed.