Insertion Sort, Algorithm Source Code for C/C++

Jun17

Insertion Sort, Algorithm Source Code for C/C++

Hello there! If you are new here, you might want to subscribe to the RSS feed for updates on this topic.

Insertion sort is one of the most common sorting algorithms you’ll ever bump into. It is very simple and it takes time roughly equal to c*n2 to sort n items, where c is an undependable constant.

Input: a sequence of n unsorted numbers

Output: a sequence of permuted n numbers from the input such that those numbers are sorted in most of the time decreasing order.

Image source: “Introduction to Algorithms”, The MIT Press

The image above explains the process used on an array of six numbers, as you can see at the end the result is a sorted array.

How it works

Indexes of numbers in this array are present above the rectangles, their connected values, on the other hand, appear in the rectangles. Have in mind that in C++ indexing starts at zero, and ends at length – 1.
In each iteration, the black rectangle represents the key taken from the current indexed number in for loop, which is being compared with all values in gray rectangles from it’s left. Gray arrows represent moving gray values one position to the right, and black arrow represent moving the key when appropriate.

Code realization

void insertion_sort(int a[], int length){
     int i, j, key;
     for(i = 1; i < length; i++){
               key = a[i];
               j = i - 1;
               while(j >= 0 && a[j] > key){
                     a[j + 1] = a[j];
                     j--;
                     }
             a[j + 1] = key;
             }
     }

void insertion_sort(int a[], int length){

int i, j, key;

for(i = 1; i < length; i++){

key = a[i];

j = i - 1;

while(j >= 0 && a[j] > key){

a[j + 1] = a[j];

j--;

}

a[j + 1] = key;

}

This function takes two parameters: the “a” array and the “length” integer that represent the number of it’s elements. It goes through the array as shown on the images and repositions it’s values so that you get a sorted array in decreasing order as an output which can be tested using printf function.

There is also a variant for getting the output in non-decreasing order:

void inverted_insertion_sort(int a[], int length){
     int i, j, key;
     for(i = length - 2; i >= 0; i--){
           key = a[i];
           j = i + 1;
           while(j <= length - 1 && a[j] > key){
                   a[j - 1] = a[j];
                   j++;
                   }
           a[j - 1] = key;
           }
     }

void inverted_insertion_sort(int a[], int length){

int i, j, key;

for(i = length - 2; i >= 0; i--){

key = a[i];

j = i + 1;

while(j <= length - 1 && a[j] > key){

a[j - 1] = a[j];

j++;

}

a[j - 1] = key;

}

This algorithm is very popular in terms of sorting short arrays, but for more complex situations you should better check out my Algorithms category and find what you need. Also, make sure to understand the code completely buy following through the function with your own example and figuring it out. Good luck!