Selection Sort

Performance of selection sort:

The worst case for selection sort occurs when the first item in the list is the largest, and the rest of the list is in order. In this case, we perform one swap on each pass through the algorithm, so the number of swaps is N. The number of comparisons is the same as in the best case, O(N ²).

The average case requires the same number of comparisons, O(N ²), and roughly N/2 swaps. Thus, the number of swaps in the average case is O(N ).

In summary, we say that selection sort is O(N ) in swaps and O(N ²) in comparisons.