WP Greet Box icon
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, most of the time, in decreasing order. 

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.

insertion sort graphic presentation Insertion Sort, Algorithm Source Code for C/C++

Code realization

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:

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 by following through the function with your own example and figuring it out. Good luck!

Like this article? Subscribe to my feed and never miss a post!

Student of Faculty of Electronic Engineering in Niš, Software/Web Developer