1 note &
Insertion Sort, Algorithm Source Code for C/C++
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 = 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 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!
