Data Exchange and Permutation Length
Lawrence A. Fialkow, Héctor N. Salas · Mathematics Magazine · 1992
A familiar theme in algorithms texts [1,2,3,6,7,8] is the estimation of runtimes for various sort routines. A more sophisticated issue, typically involving nontrivial counting arguments, is the calculation of runtimes for these algorithms. For the well-known exchange sort (or bubble sort), the texts develop the 0(n2) worst-case runtime by considering the worst-case behavior during each successive of the routine over appropriate sublists of the data list. D. Knuth [6] also develops the 0(n2) average runtime, but this cannot be based on a pass-by-pass average analysis. Perhaps for this reason, the texts neglect the average number of data exchanges occurring during a single pass of the sort. Our aim is to show that, nevertheless, this quantity has an interesting combinatorial interpretation as a measure of the average length of a permutation. Let x1. xn denote an input of n distinct real numbers. Exchange-sort transforms this list into a list sorted in increasing order via the following program: