C# Tutorial - Insertion Sort Algorithm

posted Jun 13, 2011, 9:10 AM by admin@ revitviet.vn

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

// 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.

We have already seen a version of insertion sort in the mechanism where the data was put into order for an ordered list. Strictly speaking the technique shown there is one pass of a full insertion sort.

An insertion sort is a multi-pass sort where elements are put into place by identifying the place to create a gap in a sorted sequence and inserting the item into that gap.

Consider the above data set. It is out of sorted order, and we wish to sort it using insertion sort.

Pass One

Consider the first two data items. They are out of order relative to each other, so we remove the second item from the array (by copying into a temporary variable) and slide the 35 value to the right. This will create a gap at location 0, and we can insert 19 into the gap. This results in the first two values being sorted relative to each other.

Pass Two

Now that the first two values are sorted relative to each other we can now apply the process to the first three data items:

This time we remove the third item from the array, and compare it with the data items in the already sorted section. As 35 > 24 we move the 35 one slot to the right. This moves the gap to element [1]. We next compare 24 to 19, and discover that 24 > 19. This means that the gap is in the correct place, and we can move 24 into the gap:

Pass Three

The first three elements are now sorted relative to each other, so now we examine the fourth element of the array.

Again we create a gap, this time by removing the item at index [3]. We then compare this value with the values to the left. In this case 52 > 35, so out loop terminates and 52 is assigned into the gap in the array.

As it happens this is the same location that it just vacated.

Pass Four

The first four elements of the array are now sorted relative to each other, so we turn our attention to the fifth element of the array:

This time we remove 46 from the array and slide elements right until the elements are less than the item that has been removed from the array. In this example only one item (52) is affected, leaving a gap at element [3] for us to insert 46 into. Note that the first five elements of the array are now sorted relative to each other.

Pass Five

We start by removing the sixth element from the array. We now compare this with all of the elements to the left to determine where to place it. Every time the value to the left is greater than the item we are trying to place we move that item one space to the right. In this example the value 12 is the lowest element in the array and we end up moving all of the items one slot to the right. This highlights a circumstance that we will have to consider when writing the function to perform insertion sort - if the item is the lowest in the array our technique must stop scanning left when the gap reaches slot 0. (Remember that C will not prevent you from accessing invalid array elements.)

One this pass has finished this dataset is sorted, and control can be returned to the calling function.

Now try the following task. If you have problems completing it, contact your tutor

Write a function called insertsort and add it to the program that you have developed for the previous sections. Use the function to sort the datasets generated by the program, and count how many comparisons and moves insertion sort requires to sort the data sets.