C++ Notes: Algorithms: Sort Efficiency
Bubble sorts are O(N2) on the average (and worst),
but have O(N) best case performance.
The one efficient aspect of bubble sorts is that they can quit early if the
elements are almost sorted.
Selection sorts have O(N2) efficiency.
If you need a faster sort, use Quicksort (best O(log N), average O(log N),
worst O(N2)) or heap sort (best, average, and worst are all O(log N)) in the library.