insertion bubble selection comparisonsbest case average case worst case th(nth( th( th( th( th( th( th( th( swapsbest case average case worst case th( th( th( th( th(nth(nth(nfigure comparison of the asymptotic complexities for three simple sorting algorithms the cost of exchange sorting figure summarizes the cost of insertionbubbleand selection sort in terms of their required number of comparisons and swaps in the bestaverageand worst cases the running time for each of these sorts is th( in the average and worst cases the remaining sorting algorithms presented in this are significantly better than these three under typical conditions but before continuing onit is instructive to investigate what makes these three sorts so slow the crucial bottleneck is that only adjacent records are compared thuscomparisons and moves (in all but selection sortare by single steps swapping adjacent records is called an exchange thusthese sorts are sometimes referred to as exchange sorts the cost of any exchange sort can be at best the total number of steps that the records in the array must move to reach their "correctlocation ( the number of inversions for each recordwhat is the average number of inversionsconsider list containing values define lr to be in reverse has ( - )/ distinct pairs of valueseach of which could potentially be an inversion each such pair must either be an inversion in or in lr thusthe total number of inversions in and lr together is exactly ( )/ for an average of ( )/ per list we therefore know with certainty that any sorting algorithm which limits comparisons to adjacent items will cost at least ( )/ ohm( in the average case there is slight anomaly with selection sort the supposed advantage for selection sort is its low number of swaps requiredyet selection sort' best-case number of swaps is worse than that for insertion sort or bubble sort this is because the implementation given for selection sort does not avoid swap in the case where record is already in position the reason is that it usually takes more time to repeatedly check for this situation than would be saved by avoiding such swaps