Algorithms for Complete Beginners : Insertion Sort

Part 4 : Insertion Sort

Part 1 : Introduction and Data Structures
Part 2 : Bubble Sort
Part 3 : Selection Sort

Sorting again,
    Sorry to disapoint but i had no choice because this sorting also uses the Array data structure so doing it straightaway is better than comming back later. So let's see about the insertion sort, again a not-so-good sorting with some of uses of its kind and move onto a whole new brand of algorithms.

Insertion Sort

   Like most of the sorting algorithms, this too has the core concept of "swapping: but instead of saving the swaps  like in the Selection Sort, this algorithm concerns more about saving the times which the inner loops will run, saving us some valuable CPU calls at the same time dedicating swaps. however the algorthims is know the be really efficient for part sorted, or almost sorted arrays or sequence in which the time taken for sorting would decrease drastically when compared to other Bubble Sort and Selection Sort which have a const time for the sorting in most of the cases.

How Insertion Sort works?

Image from wiki article

As i said early, this one concerns about saving out time. Basically, it will go through the sequence checking each element starting from the second onwards, and for each element, it will loop back the array to search for the best place for the number to be. In more common terms it backtracks will it find the exact spot, where the current number should belong and put it there. But along with the backtracking, it actually swaps each intermediate element, so in the end of one main cycle the whole sequence has  a change. It would be easier to get the idea behind with an example.

ex: Sort an array of numbers using Insertion Sort

{5,6,2,3,4} We start off with the second element that is, 5
{6,5,2,3,4} We start by backtracking from the element before the selected, that is 6. The condition for the backtracking to end is that either the item being backtracked [compared to the selected element] is lower than the selected or the start of the array is reached [that is the index no of the backtrack is 0]
{5,6,2,3,4} As 6 > 5 and 6's index no is 1, the swap is done between 5 & 6. Still the backtracking hasnt ended.
{5,6,2,3,4} We check what's the one before 5 now, ah it is the start if the array, now we can safely put the END IT signal and goto the next element, that is third [index no. 2], 2.
{5,2,6,3,4} When 2 is compared with 6, as 6 > 2 they are swapped
{2,5,6,3,4} When 2 is compared with 5, as 5 > 2, they are swapped
{2,5,6,3,4} Ouch! the start of the array, so the loop ends.
Like wise it goes till the last element is processed like this.
{2,3,4,5,6} We get this after all, BIG DEAL! :D

Pseudo-code

1. S : sequence of sortable items
2. N : no of items
4. for i = 1 to N-1 do
5.         j = i-1;
6.         temp = S[i];
8.         while j>=0 and S[j] > temp
9.                 S[j+1] = S[j];
10.                 j = j-1;       
11.         end while
13.         S[j+1] = temp;
14. end for

Explanation

First we take S, the sequence of sortable, comparable items, in this case an array of integers. N, no. of elements.
Line 4: we take the main loop, starting to proccess from the second element onwards. Why second element is need to backtrack and if we start with first element we have no chance of backtracking as it is the start :D
Line 5: We take j as the starting point of backtracking, we dont need to compare with the current item so we start with item one behind the current
Line 6: For future use, the current element is saved to a temp variable
Line 8: THE MOST IMPORTANT, we start the backtracking, the conditions are vital it to be successful, we search backwards till either the searched item is less than the current [so that obviously the the current should come after the searched] or the we reach the start of the array.
Line 9-10: Swapping and then reducing the value of j.
Line 13: At the end of each loop we need to remember on thing, now our selected element has no place as it was swapped to one behind in the process, so the variable j holds ONE ELEMENT BEFORE THE EXACT place where the current one should actually be. Why one before is that an additional j-1 is executed due to the way while loop works. [no way i'm explaining that as well]. So at the end of the main loop, we put the current element to rightly chosen place, the sorted place.

Ahh lets get to the geek part ;)

Insertion Sort Implementation in C++

1. #include<iostream>
3. using namespace std;
5. int main(){
6.     int S[] = {20,30,50,40,65,10};
7.     int N = sizeof(S)/sizeof(int);
8.    
9.     for(int i=1;i<N;i++){
10.             int j = i-1;
11.             int temp = S[i];
12.            
13.             while( j >= 0 && S[j] > temp ){
14.                    S[j+1] = S[j];
15.                    j--;
16.             }
17.            
18.             S[j+1] = temp;
19.     }
20.    
21.     for(int i=0;i<N;i++){
22.             cout << S[i] << " ";        
23.     }
24. }

Insertion Sort Implementation in Java

1. class InsertionSort{
2.         public static void main(String args[]){
3.                 int S[] = {20,30,50,40,65,10};
4.                 int N = S.length;
5.                
6.                 for(int i=1;i<N;i++){
7.                         int j = i-1;
8.                         int temp = S[i];
9.                        
10.                         while( j >=0 && S[j] > temp ){
11.                                 S[j+1] = S[j];
12.                                 j--;
13.                         }
14.                        
15.                         S[j+1] = temp;
16.                 }
17.                
18.                 for(int x:S){
19.                         System.out.print(x + " ");
20.                 }
21.         }
22. }

Output : 10 20 30 40 50 65

Efficiency of Insertion Sort

For this one, i have very little to talk,as the algorithm it self is more likely the other two, meaning they give the usual n^2 in worst cases. But remember that if this is a sorted array we are trying to sort, while all the other two will run more than n time, this will run smoothly only in n time and end, and for that only we can give the credit :)

Worst Case: O(n²)
Average Case: O(n²)
Best Case: O(n)


Now, i'm serious this time that the next WONT be another sorting, and well you have put the array into some good use, may be need something with more power next time.
Wait for it :D