Insertion Sort Algorithm

The insertion sort only passes through the array once. Therefore it is a very fast and efficient sorting algorithm with small arrays. (The efficiency is lost however with large amounts of data.)

The sort works as follows: the array is split into two (virtual) sub-arrays. (With virtual I mean that the array is not really split.) The first sub-array is considered to be the “sorted array”. The elements of the second sub-array will be inserted into the first sub-array at the right position.

Take look at the selection sort source code example:

#include<iostream>
using namespace std;

int main(void)
{
	int array[5];		// An array of integers.
	int length = 5;		// Lenght of the array.
	int i, j;
	int keyelement;

	//Some input
	for (i = 0; i < length; i++)
	{
		cout << "Enter a number: ";
		cin >> array[i];
	}

	//Algorithm
	for(j = 1; j < length; j++) // Note!
	{
		keyelement = array[j];
		for (i = j - 1; (i >= 0) && (array[i] < keyelement); i--)
		{
			array[i+1] = array[i];
		}
		array[i+1] = keyelement;
	}

	//Some output
	for (i = 0; i < 5; i++)
	{
		cout << array[i] << endl;
	}
}

Note: as you can see, the array starts with one not zero.

That is all for this tutorial.