Average number of required swaps in selection sort

Question

Assume that the distinct integers 1,...,N are in random order and need to be sorted using selection sort. Here I am interested in the average number of swaps required, rather than the number of comparisons. Self-swaps are not counted. Running the selection sort over every possible permutation for a given N provides the following average number of swaps:

        N        Total swaps     Average number of swaps

        2        1               0.5
        3        7               1.1667
        4        46              1.9167
        5        326             2.7167
        6        2556            3.5500
        7        22,212          4.4071
        8        212,976         5.2821
        9        2,239,344       6.1710

Is there a formula for the total or average number of required swaps? A linear least-squares fit produces $$ 0.816411N - 1.27647 $$ for the average, but it is inexact. The code presented at https://en.wikipedia.org/wiki/Selection_sort#Implementations was used.

Answer 1

Among $N!$ permutations, $(N-1)!$ of them have the minimal element in the correct position, and do not require a swap; $N1 - (N-1)!$ do require it. That is, the average number of swaps to place the first element is $1 - \dfrac{1}{N}$, and then you are left with a random set of $N-1$ elements. That is, an average number of swaps is $S_N = 1 - \dfrac{1}{N} + A_{N-1}$. Expanding, obtain $S_N = N - H_N \approx N - \ln N - \gamma$