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.

This entry was posted in Programming Algorithms. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. Tweet This! Tweet This! or use to share this post with others.

Leave a Reply: