Insertion Sort Algorithm

11 12 2007

he Insertion sort works just like its name suggests – it inserts each item into its proper place in the final list. The simplest implementation of this requires two list structures – the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.The Insertion sort is a little over twice as efficient as the bubble sort.

The insertion sort is a good middle-of-the-road choice for sorting lists of a few thousand items or less. The algorithm is significantly simpler than the shell sort, with only a small trade-off in efficiency. At the same time, the insertion sort is over twice as fast as the bubble sort and almost 40% faster than the selection sort. The insertion sort shouldn’t be used for sorting lists larger than a couple thousand items or repetitive sorting of lists larger than a couple hundred items.

Insertion Sort Routine

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Insertion Sort Algorithm
public void sortArray()
{
int i;
int j;
int index;

for( i = 1; i < x; i++ )
{
index = a[i];
j = i;

while( (j > 0) && (a[j-1] > index) )
{
a[j] = a[j-1];
j = j – 1;
}

a[j] = index;
}
}

You can download the full code here, or the compiled code here.

further : http://www.publicjoe.f9.co.uk

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: