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 :




Leave a Reply

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

You are commenting using your 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: