Consider running the Selection sort algorithm on a permutation $p$ of $n$ elements. Let $f(p)$ denote the number of times the 'running minimum' changes throughout the algorithm. Conjecture: $f(p)$ is maximised for $p = (n, n-1, \ldots, 1)$.
For clarification, I will calculate $f(3, 4, 2, 1)$:
Running minimum changes during the first sweep: $3 \rightarrow 2$, $2 \rightarrow 1$.
Permutation after the first sweep: $(1, 4, 2, 3)$.
Running minimum changes during the second sweep: $4 \rightarrow 2$.
Permutation after the second sweep: $(1, 2, 4, 3)$.
Running minimum changes during the third sweep: $4 \rightarrow 3$.
Permutation after the third sweep: $(1, 2, 3, 4)$.
Thus, $f(3, 4, 2, 1) = 4$.
I have verified that the conjecture holds for $n \leq 12$ using a brute force approach, but it's infeasable to try and verify for bigger $n$ as the algorithm runs in $O(n^2n!)$. Using a modification of the same algorithm, I was also able to show that the following statement which might have been used as an 'exchange argument' doesn't hold:
For all permutations $p \neq (n, n-1, \ldots, 1)$, there exist $i, j$, with $i < j$ such that $p_i < p_j$ and swapping $p_i$ and $p_j$ yields a permutation $r$ such that $f(r) \geq f(p)$.
Though I haven't been able to disprove the above statement only applied to permutations $p$ such that $f(p)$ is maximised.
If anyone is interested, this is the sequence of values for $f(n, n-1, \ldots, 1)$.
Edit:
Haven't made much progress, but I have found another interesting property via brute force which shows that there is some regularity to the permutations maximising $f$:
Consider a permutation $p$. Define the function $g_p(x): [n] \rightarrow \mathbb{N}$ as follows:
$g_p(x)$ is the number of times that $x$ changes the running minimum value when the algorithm is run on the permutation $p$. For example, letting $p=(3, 4, 2, 1)$, we have $g_p(2) = 2$, as $2$ changed the running minimum twice.
I have verified that the following holds for all $n \leq 12$: for any two permutations $p$ and $r$ maximising $f$, $g_p$ and $g_r$ are permutations of each other. More formally, there exists a bijection $\sigma(x): [n] \rightarrow [n]$ such that $\forall x \in [n],\ g_p(\sigma(x)) = g_r(x)$.
More informatively, for all permutations $p$ maximising $f$: $g_p(n) = 0$ and $\forall k \in \{1, \ldots, \left \lfloor \frac{n-1}{2} \right \rfloor \}$, there exist exactly two $x \in [n]$ such that $g_p(x) = k$. The value $\left \lfloor \frac{n-1}{2} \right \rfloor + 1$ either appears exactly once or doesn't appear, based on the parity of $n$.
Best Answer
I finally did it:
Fix a permutation $p$ of $n$ elements. Let $p_i$ denote the permutation in the $i$-th step of the algorithm when run on permutation $p$. (I will denote the $i$-th element of permutation $p$ with $p(i)$).
In particular, $p_1 = p,\ p_n=(1,2,\ldots,n)$. Now we note that the number of running minimum changes of the algorithm in step $i$ is at most $\min(p_i(i) - i, p^{-1}_i(i) - i)=\min(p_i(i),p^{-1}_i(i))-i$.
This can be shown by noting that the running minimum at step $i$ cannot change more than $p_i(i) - i$ times (as it starts with value $p_i(i)$ and ends with value $i$), and it also cannot change more than $p^{-1}_i(i) - i$ times (as we start at position $i$ and end at position $p^{-1}_i(i)$).
Now, we have: $$f(p) \leq \sum_{i = 1}^n \min(p_i(i), p^{-1}_i(i)) - i$$
Let $P_k(i): \min(p_i(i), p^{-1}_i(i)) = k$.
Claim: For all $k$, we cannot have $P_k(i)$ for more than two $i$.
Proof:
Fix $k$.
Let $i_1,\ i_2,\ i_1 < i_2$ be the smallest numbers such that $P_k(i_1)$ and $P_k(i_2)$ hold.
Case $1$: $p_{i_1}(i_1) = k \land p^{-1}_{i_1}(i_1) = k$
Trivial.
Case $2$: $p_{i_1}(i_1) = k \land p^{-1}_{i_1}(i_1) > k$
We can see that $p_{i_2}(i_2) \neq k$ as $p^{-1}_j(k) > k$ for any $j$ with $i_1 < j \leq k$.
Thus, $p_{i_2}(i_2) > k \land p^{-1}_{i_2}(i_2) = k$.
Now it's not hard to see that: $$\forall j > i_2,\ p_j(j) \neq k \land p^{-1}_j(j) \neq k$$
Case $3$: $p_{i_1}(i_1) > k \land p^{-1}_{i_1}(i_1) = k$
We can see that $p^{-1}_{i_2}(i_2) \neq k$ as $p_j(k) > k$ for any $j$ with $i_1 < j \leq k$.
Thus, $p_{i_2}(i_2) = k \land p^{-1}_{i_2}(i_2) > k$.
Again, it's not hard to see that: $$\forall j > i_2,\ p_j(j) \neq k \land p^{-1}_j(j) \neq k$$
Now with this claim we get: $$f(p) \leq -\left (\sum_{i=1}^n i \right ) + 2n + 2(n-1) + \ldots = \left \lfloor \frac{n}{2} \right \rfloor \cdot \left \lceil \frac{n}{2} \right \rceil$$
As $f(n, n-1, \ldots, 1) = \left \lfloor \frac{n}{2} \right \rfloor \cdot \left \lceil \frac{n}{2} \right \rceil$ we are done.
Little fun fact: $$\forall p,\ f(p) = f(p^{-1})$$