Classifying the Sorts We Have Written

We have now written three sorting algorithms and counted each one’s comparisons and swaps. Let’s put the counts side by side.

The first table counts comparisons. Bubble sort here is the version with early termination.

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$

The second table counts swaps. Selection sort here is the version that skips a swap of an element with itself.

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

Comparisons and swaps measure time. A sort also has properties that the counts do not show. The first is space. Recall that an algorithm works in place when it modifies its input using $O (1)$ auxiliary space. All three of these sorts do. Each one moves elements around inside the array it was given, and the only extra memory is a few local variables, such as temp in the swap. Not every sort works in place. Merge sort, in the next chapter, needs a second array as large as the input.

Other properties of a sort are stability, adaptivity, and cache locality. The next section is about stability. We will need it again when we write merge sort in the next chapter. The others come up in later chapters, when we write more sorts.