Insertion sort in C++

Insertion sort is another sorting technique used when sorting arrays. Unlike bubble sort, it uses much less number of passes to sort an array. As the name suggests, sorting is done by inserting elements in their proper order by comparing an element with the elements on either side. Hers is how it works. Suppose we want to sort an array A with elements A[1],A[2]....A[N]. Then,
Step 1 : A[1] by itself is trivially sorted.
Step 2 : A[2] is inserted either before or after A[1] so that A[1],A[2] are sorted.
Step 3 : A[3] is inserted into proper place in A[1],A[2],that is, before A[1], between A[1]
and A[2, or after A[2], so that A[1],A[2],A[3] is sorted.
The process keeps repeating until the array is fully sorted.

The following program demonstrates the use of insertion sort by sorting an array of integers in ascending order

// Program to implement insertion sort ( ascending order )
#include <iostream>

void Insertion_sort(int AR[],int n)
{
     int temp,j;
     AR[0] = INT_MIN;
     for (int i=1; i<=n; i++)
     {
          temp = AR[i];
          j = i-1;
          while ( temp < AR[j])
          {
               AR[j+1] = AR[j];
               j--;
          }
          AR[j+1] = temp;
     } // end of for loop
} // end of insertion sort function

int main()
{
     int arr[20];
     int size;
     std::cout<<" Enter the maximum no. of elements you want (max 20) : ";
     std::cin>>size;
     std::cout<<"\n Now enter the elements in the array \n ";
     // loop to prompt the user to enter the elements in the array
     // notice that the elements are inserted fromt he 1st index rather that 0, as 0 index will be assigned 
     // INT_MIN value from which other elements will be compared
     for (int i=1; i<=size; i++)
     {
          std::cout<<"Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     Insertion_sort(arr,size);
     // as arrays are passed with reference, hence any changes will be reflected in the original array as well
     std::cout<<" \n The sorted array is as follows \n ";
     for (int i=1; i<=size; i++)
     {
          std::cout<<" \n Element "<<i<<" : "<<arr[i];
     }
     return 0;
} // end of main
------ OUTPUT ------

------Programming Advice and Tips------

1 - Even though insertion sort uses considerably less number of passes to sort an array, it still is not useful

when sorting arrays that contain large number of elements. Hence it is best advised to use insertion sort

where the no of elements to be sorted are less(i.e having small value of N).

2 - Notice that all the loops start from index location 1 rather than starting from 0 (which is usually done). This is done because, at the 0th index location, INT_MIN value is stored from which other elements are compared and is vital in terminating the while loop.

3 - INT_MIN is the MINIMUM value that an integer can have. It is usually a negative value, and varies from platform to platform.

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.


------ Related Posts ------

Bubble Sort in C++ : http://programsplusplus.blogspot.in/2012/02/bubble-sort-in-c.html
Selection Sort in C++ : http://programsplusplus.blogspot.in/2012/02/selection-sort-in-c.html