4.1. The Cost of Exchange Sorting¶
4.1.1. The Cost of Exchange Sorting¶
Here is a summary for the cost of Insertion Sort, Bubble Sort, and Selection Sort in terms of their required number of comparisons and swaps in the best, average, and worst cases. The running time for each of these sorts is \(\Theta(n^2)\) in the average and worst cases.
Most “good” sorting algorithms have average case running times that are significantly better than these three under typical conditions. But before studying those, it is instructive to investigate what makes these three sorts so slow. The crucial bottleneck is that only adjacent records are compared and swapped. This means that moves (for Insertion and Bubble Sort) are by single steps. Swapping adjacent records is called an exchange. Thus, these sorts are sometimes referred to as an exchange sort. The cost of any exchange sort can be at best the total number of comparisons that the records in the array must make, which turns out to have a lot to do with how far they are from their “correct” location. The total number of comparisons required is at least the number of inversions for the record, where an inversion occurs when a record with key value greater than the current record’s key value appears before it.
