The Locked Library

Worst case: 6 swaps (when all 7 books form one cycle). Best case: 0 swaps (already sorted). Average: 7 - H(7) ≈ 4.41 swaps, where H(7) ≈ 2.59 is the 7th harmonic number. Formula: minimum swaps = n - (number of cycles in the permutation).

Every permutation decomposes uniquely into disjoint cycles. A cycle of length k (meaning k elements form a closed loop) requires exactly k-1 swaps to fix. Total swaps = sum over all cycles of (cycle_length - 1) = n - (number of cycles). Step 1: Example: permutation (2,3,1,5,4,6,7) decomposes into cycles. Books 1→2→3→1 (cycle of length 3) and 4→5→4 (cycle of length 2) and 6→6 (fixed point, length 1) and 7→7 (fixed point, length 1). Step 2: Swaps needed: (3-1) + (2-1) + (1-1) + (1-1) = 2+1+0+0 = 3 swaps. Step 3: Worst case: single cycle of length 7 (all 7 books in one big loop). Swaps = 7-1 = 6. Step 4: Best case: identity permutation (already sorted) or all fixed points. Swaps = 0. Step 5: Average number of cycles in a random permutation of n elements = H(n) = 1 + 1/2 + 1/3 + ... + 1/n (the nth harmonic number). For n=7: H(7) = 1 + 0.5 + 0.333 + 0.25 + 0.2 + 0.167 + 0.143 ≈ 2.593. Step 6: Average swaps = n - H(n) = 7 - 2.593 ≈ 4.41 swaps on average. Key Insight: The connection between sorting swaps and permutation cycles is one of the most beautiful results in combinatorics. The harmonic number H(n) appearing as the expected number of cycles links sorting theory to the analysis of algorithms. This result also appears in the analysis of Quicksort and in the study of random permutations.