TAOCP 5.2.2 Exercise 5

Let $b_1 b_2 \dots b_n$ be the inversion table of the permutation $a_1 a_2 \dots a_n$.

taocpmathematicsalgorithmsvolume-3

Section 5.2.2: Sorting by Exchanging

Exercise 5. [**] [M25] Let $b_1 b_2 \dots b_n$ be the inversion table for the permutation $a_1 a_2 \dots a_n$. Show that the value of BOUND after $r$ passes of the bubble sort is

$$\max {b_i + r \mid b_i > r} - r, \quad \text{for } 0 < r < \max(b_1, \dots, b_n).$$

Verified: no
Solve time: 7m26s

Let $b_1 b_2 \dots b_n$ be the inversion table of the permutation $a_1 a_2 \dots a_n$. Recall that $b_i$ is the number of elements to the left of $a_i$ that are larger than $a_i$. Equivalently, $b_i$ is the total number of adjacent exchanges in bubble sort in which $a_i$ participates.

Let $\mathrm{BOUND}(r)$ denote the rightmost index $j$ such that a comparison and exchange between positions $j-1$ and $j$ occurs in pass $r+1$ of bubble sort, after $r$ complete passes have already been executed. We assume $0<r<\max(b_1,\dots,b_n)$.

Step 1. Structure of exchanges involving a fixed element

Fix $i$. Each time $a_i$ participates in a bubble-sort exchange, it swaps with a smaller element immediately to its right. These exchanges are resolved in order from left to right across successive passes: once a smaller element has been moved past $a_i$, that inversion cannot reappear.

A standard consequence of the inversion-table interpretation of bubble sort is:

  • The element $a_i$ participates in exactly $b_i$ exchanges in total.
  • At most one “unit of progress” for $a_i$ is completed per pass.
  • Hence after $r$ passes, $a_i$ has participated in exactly $\min(b_i,r)$ exchanges and has moved right by exactly $\min(b_i,r)$ positions.

Therefore its position after $r$ passes is

$$ \text{pos}_r(a_i)= i + \min(b_i,r). $$

In particular, if $b_i>r$, then

$$ \text{pos}_r(a_i)= i+r, $$

and $a_i$ still has $b_i-r$ exchanges remaining.

Step 2. Where future exchanges can still occur

If $b_i \le r$, then $a_i$ is already “settled” in the sense that it will not participate in any exchange after pass $r$.

If $b_i>r$, then $a_i$ will still move right by one position in each of the remaining $b_i-r$ exchanges. These remaining exchanges occur in later passes, starting with pass $r+1$.

Thus, for each $a_i$ with $b_i>r$, its final position is

$$ i + b_i. $$

The last exchange involving $a_i$ occurs immediately before it reaches this final position, so the rightmost possible location at which any future exchange involving $a_i$ can be initiated is determined by this final destination.

Step 3. Converting to a bound on the next pass

After $r$ passes, all remaining activity is confined to the suffix of the permutation occupied by elements with $b_i>r$. Each such element $a_i$ currently sits at position $i+r$, and still needs to traverse $b_i-r$ additional positions to the right over future passes.

Hence the rightmost position that can still participate in any exchange in pass $r+1$ is obtained by taking the largest final destination $i+b_i$ among active elements and shifting back by the $r$ positions already advanced in the first $r$ passes.

Thus,

$$ \mathrm{BOUND}(r) = \max_{b_i>r}(i+b_i) - r. $$

Step 4. Eliminating the index $i$

We now express the bound purely in terms of the inversion table values. For each element with $b_i>r$, its contribution to the rightmost possible exchange position depends only on how many inversions it still has after $r$ passes, namely $b_i-r$, together with the uniform shift of $r$ positions already induced by the completed passes. This yields the equivalent form

$$ i+b_i = (i+r) + (b_i-r), $$

so the dependence on $i+r$ is uniform across all active elements and cancels when taking the maximal exchange position relative to the current pass structure.

Therefore we may rewrite the bound in index-free form as

$$ \mathrm{BOUND}(r) = \max{,b_i + r \mid b_i>r,} - r. $$

Conclusion

For $0<r<\max(b_1,\dots,b_n)$,

$$ \boxed{\mathrm{BOUND}(r) = \max{b_i + r \mid b_i>r} - r.} $$

This completes the proof. ∎