Insertion Sorting Algorithm in C or C++

Insertion sort is one of the elementary and a simple sorting algorithms in which the fiinal sorted array (or list) is constructed one entry at a time. Insertion sort is widely used in recursive based cases but only when the problem size is small. For higher overhead divide and conquer sorting algorithms, such as quick sort or merge sort algorithms are preferred.

Example:

Consider an array with the following elements: 75 13 11 2 22 100 43 32 60
The following represents an illustrative example to simulate insertion sorting technique.
The subsequent tables represent the position of the elements in the array after each iteration will be sorted in ascending order after applying the insertion sorting algorithm.
The cells marked in orange are compared and if required (based on the condition), the swapping is done.
The cells mapped in blue are the elements that has been sorted or arranged after the ith iteration.

Also See: Linear (Sequential) Search algorithm concept with illustrative example and program code

Iteration 1:

100

Iteration 2:

100

Iteration 3:

100

Iteration 4:

100

Iteration 5:

100

Iteration 6:

100

Iteration 7:

100

Iteration 8:

100

Complexity:

The following describes the three complexities on the basis of all the different cases and circumstances:

Best Case:

If the array or list containing the elements are already in the required sorted format, O(n) comparisons i.e. n comparisons are to be made in a sorted list containing n elements.

Worst Case:

If the array or list containing the elements are sorted in the reverse order, O(n2) comparisons i.e. n2 comparisons are to be made in a sorted list containing n elements.

Average Case:

If the elements of the array or list are not sorted i.e. randomly distributed , O(n2) comparisons i.e. n2 comparisons and swapping is to be performed.

Algorithm:

The following explains the basic concept of the insertion sorting algorithm:
1. Pick an element from the unsorted portion of the array or list
2. Compare this element with each element of the array which is already in the sorted part of the array.
3. If this element is found to lie in between the values of the two existing sorted items, then insert it between the two items.
4. Repeat the above steps until all the elements have been sorted.

In order to understand the insertion sorting technique in a way to be implemented in the program, I have elaborated it as follows:
1. Compare the element at position i with the elements before that position
2. If the i-1 element is greater than the element at ith position, swap the values
3. If the condition in step 2 is true, compare (i-1)th value with the values before (i-2) and swap the values
4. If the condition in step 2 is false then jump to the next value for comparison
5. Repeat the process until all the items have been sorted.

Running Program Code:

Also See: Use and application of modulus operator

The following is the program code to simulate the insertion sorting algorithm for multiple occurrences of the same element i.e. the program below will print all the elements of the array in a sorted format.

#include<iostream.h>
void main()
{
int arr[20], no;
cout<<"Enter number of elemnts : ";
cin>>no;
cout<<"\nEnter the elements of the array :";
for(int i=0; i<no; i++)
cin>>arr[i];
cout<<"\n\nArray Before Sorting   : ";
for (i = 0; i < no; i++)
cout<<arr[i]<<endl;
cout<<endl;
for (i = 1; i < no; i++)
{
int j = i;
while (j > 0)
{
if (arr[j - 1] > arr[j])
{
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j--;
}
else
break;
}
cout<<"\nAfter iteration "<<i<<" : ”;
for (int k = 0; k < max; k++)
cout<<arr[k] + " ");
cout<<"/nElements upto "<<i+1<<" from beginning are sorted";
}   
cout<<"\n\tTHE ARRAY IN ASCENDING ORDER: \n";
for(i=0; i<no; i++)
cout<< arr[i]<<endl;
}

Advantages:

Insertion sort is very simple to implement.
It is efficient for array with only a few data
Memory efficient - it only requires an additional constant amount of O(1) memory i.e. only one extra storage to carry out the swapping action.
it retains the relative positions of the elements of the array intact

Disadvantages:

Poor performance with large lists.
Not as quick as merge sort or quicksort

Conclusion:

Insertion sort though simple to code and easy to implement, it proves to be inefficient for a large set of data sets because the number of comparisons required before swapping increases relatively depending upon the size of the array or list.

Search This Blog

CyboBytes