Thursday, July 29, 2010

ASP.NET-Insertion Sort

 Insertion Sort


The 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 Code


// 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;
}
}

No comments:

Post a Comment