Introduction
When we need to perform sorting on a list of elements then Insertion Sort is one of the basic algorithms which can be used. It’s simple but as we will see it’s not very efficient.
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists. –Wiki
It’s quite similar to the way we sort playing cards in our hand. It involves comparison and movement for each of the elements. It uses two loops. That’s the reason worst case complexity is O(N²) (you can read about “Big O” notation here). The best case scenario means that the list is already sorted. So we only perform comparison and no movements. That gives us a time complexity of O(N).
Let’s look at the Algorithm
Suppose we have a list of numbers 4,2,3,5,1,7 and we want to sort these.
- Put elements in an Array. Say array name is input. Code : int input = {4,2,3,5,1,7};
- Start with the second index i.e. input[1] which has a value 2. Let’s denote this as “current_number“.
- Run a loop in reverse.
- Compare current_number with each of the numbers prior to it. If it’s less than any then shift or move the element to right. At the end of this iteration we will find a place for current_number.
- Repeat this Procedure for all elements in the Array.
The C Program below will help you understand this better.
Why Android 