Comparing the Sorts and Stability

Exercise

Fill in this table of comparison counts for selection sort, bubble sort with early termination, and insertion sort, on an array of $n$ elements.

Algorithm	Sorted	Reverse sorted	Random
Selection sort
Bubble sort
Insertion sort

Solution

Algorithm	Sorted	Reverse sorted	Random
Selection sort	$\frac{n ( n - 1 )}{2}$	$\frac{n ( n - 1 )}{2}$	$\frac{n ( n - 1 )}{2}$
Bubble sort	$n - 1$	$\frac{n ( n - 1 )}{2}$	about $\frac{n ( n - 1 )}{2}$
Insertion sort	$n - 1$	$\frac{n ( n - 1 )}{2}$	about $\frac{n ( n - 1 )}{4} + n$

Solution

Bubble sort and insertion sort. Their comparison counts differ between sorted and reverse-sorted input, so the input order changes the running time. Selection sort’s count is the same in every column: it scans the whole unsorted portion for the largest element on every pass, whatever the order.

Solution

Bubble sort and insertion sort both make one swap per inversion in the input, so they always swap the same number of times. Selection sort makes at most $n - 1$ swaps.

Solution

A sort is stable if elements that compare equal keep their original relative order. Sorting playing cards by rank: if the seven of hearts comes before the seven of clubs in the input, a stable sort keeps it before; an unstable sort may flip them, and the suits show that it did. Two equal int values are interchangeable, so swapping them changes nothing you can observe.

Solution

Selection sort is not stable: swapping the minimum into position can carry an element past an equal one. Bubble sort is stable: it swaps only adjacent elements, and only when the left one is strictly greater. Insertion sort is stable: the inner loop stops at an element equal to the key, so the key lands after it.

Exercise

Here is an insertion sort whose inner loop uses >= instead of >:

public static void insertionSort(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i;
    while (j > 0 && arr[j - 1] >= key) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = key;
  }
}

Does it sort correctly? Is it stable?

Solution

It sorts correctly. It is not stable: the key now shifts past elements equal to it and lands in front of them, reversing their original order.