Efficiency of straight selection sort

Straight selection sort finds the smallest element of the unsorted part in each pass and swaps it into its place.

For n elements, pass 1 makes n−1 comparisons, pass 2 makes n−2, ..., and the last pass makes 1:

(n−1) + (n−2) + ... + 1 = n(n−1)/2 = (n² − n)/2

So the number of comparisons is about n²/2 in every case (best, average and worst), because the whole unsorted part is always scanned. Swaps are at most n−1.

Answer: time complexity is O(n²) in all cases; extra space is O(1).