Comparing Performance of Insertion Sort and Selection Sort

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Does Insertion Sort always outperform Selection Sort? Or vice versa? If not always, under what conditions one would become faster than the other? In this article, we will observe the factors aﬀecting performance of these two sorting algorithms, and see examples where one of them outperforms the other.

An implementation of the two sorting algorithms in C has been provided below. The input array a[] of n elements of type object (an structure) needs to be sorted in ascending order, using the comparison function less_than(). We will be denoting any subarray of a[] from some index x to some index y (y ≥ x) as a[x : y].

typedef struct object
{
  unsigned int key;
  short        field1;
  char         field2[2];
  int          more_fields[2];
} object;

#define less_than(o1, o2) (o1.key < o2.key)

void insertion_sort(object a[], int n)
{
  int    i, j;
  object t;

  i = 1;

  /* loop-invariants (specified for case n > 0):
       P: a[0:i-1] contains same elements as the initial a[0:i-1]
       Q: a[0:i-1] is sorted */

  while(i < n)
  {
    /* create hole (position that can be overwritten) at index i */
    t = a[i];
    j = i;

    /* loop-invariants:
         R: the "hole" is at index j
         S: t is less than each element in a[j+1:i] */

    while(j >= 1 && less_than(t, a[j-1]))
    {
      a[j] = a[j-1];
      j = j-1;
    }

    /* copy t to the hole at index j */
    a[j] = t;

    i++;
  }

  /* P and Q hold with (i = n) */
}

void selection_sort(object a[], int n)
{
  int    i, j, min;
  object t;

  i = 0;

  /* loop-invariants:
       P: a[0:i-1] contains the i smallest elements of initial a[]
       Q: a[0:i-1] is sorted */

  while(i < n-1)
  {
    min = i;
    j = i+1;

    /* loop-invariant R: a[min] is minimum in a[i:j-1] */

    while(j < n)
    {
      if(less_than(a[j], a[min]))
        min = j;

      j = j+1;
    }

    /* R holds with (j = n) */

    if(min != i)
    {
      /* swap a[i] and a[min] */
      t = a[i];
      a[i] = a[min];
      a[min] = t;
    }

    i++;
  }

  /* P and Q hold with (i = n-1) */
  /* Now a[n-1] must be among the largest, so a[0:n-1] is sorted */
}