selection sort running time confusion

Question

According to http://algs4.cs.princeton.edu/21elementary/ "Selection sort uses ~N²/2 compares and N exchanges to sort an array of length N."
For example I have two items in the array.
String[] a = {"h","t"};
Can I asume that selection sort uses 2²/2 = 2 compares and 2 exchanges to sort an array of length 2?
But when I run this: http://algs4.cs.princeton.edu/21elementary/Selection.java.html It only compared once. Of course it's common sence because the only items to compare are h and t. But I'm still confused by the statement. Is their something wrong with my experiment? I'm new at this.

Answer 1

Selection sort uses approximately N^2/2 comparisons and N exchanges.

For an exact analysis, selection sort uses

N-1 + N-2 + N-3 + .....1 comparisons to sort an array of length N.

Thus total number of comparisons = (N-1)*(N)/2 = N^2/2 - N/2 which is approximately equal to N^2/2 . Which is what they have written.

In your example when N is 2, comparisons = 1*2/2 = 1. And the number of exchanges is = 1. (N-1)

Answer 2

The notation f(n) ~ g(n) means: $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1 $$

In this particular case, you see that the first element is compared to other $n - 1$, the second to $n - 2$, until the next-to-last with 1. So the number of comparisons is:

(n - 1) + (n - 2) + ... + 1 = n (n - 1) / 2 ~ n^2 / 2