# Optimal Algorithms for Sorting Permutations with Brooms
## 3 Sorting Permutations with a Single Broom
### Correctness of \(A_{b}\)
In every swap on the path edge involving at least one path marker, the larger of the markers will move to the right. Proof. : Considering the contradiction of the stated property, a _bad swap_ involves moving a smaller valued path marker to the right and larger valued path marker to the left. Suppose \(S\) contains a bad swap. We show how \(S\) can be modified to obtain a new swap sequence which contains fewer swaps on the path. Assume smaller marker \(s\) is swapped to the right and larger marker \(l\) to the left. Property \(1\) restricts us from directly swapping them again. Therefore, marker \(l\) will move to the star leaf, then marker \(s\) to another star leaf and then \(l\) goes to the center of the star. Let us call this intermediate placement as \(S^{\prime}\). Now, to modify \(S\), remove the swap of \(s\) and \(l\), and continue with the preceding swaps with \(s\) and \(l\) exchanged until the state \(S^{\prime}\) is reached. We have achieved the same target state, but a swap carried out on the path is removed and compensated for by adding an additional swap in the star; hence, reducing the swap count on the path edge. 5. No star marker moves past the first path edge from left to right. Proof. : Let \(S\) include a swap \(S_{i}\) in which a maker \(x\) moves past the first path edge to the right using a swap with a marker \(p\). Let, \(S_{i}\) is a swap belonging to \(S\) where \(j>i\) which results in \(x\) reentering the star with the help of a swap with \(q\). Taking the least  
Figure 4: (a) S = (1, 2), (2, 6), (2, 3), (1, 6), (1, 3), (1, 4). (b) Modified Swap Sequence = (1, 6), (1, 3), (2, 6), (2, 3). possible \(j\) into account, we first establish that the marker \(q\) was residing on the star leaf during \(S_{i}\). Suppose \(q\) was on path node during \(S_{i}\), then \(q\) will lie on the right to \(x\). Swaps involving \(x\) between \(S_{i}\) and \(S_{j}\) will only keep it on path nodes and not move it past the first path edge as per our assumption. Marker \(q\) is restricted to swap twice with \(x\) on the path edge as per Property 1, which proves that \(q\) lies on the right of \(x\) during \(S_{j}\), which is contradictory. We show how \(S\) can be modified to obtain a swap sequence with a lesser number of swaps on the path. Before \(S_{i}\), carry out a swap of \(x\) and \(q\) and continue with the following swaps till \(S_{j}-1\) with \(x\) replaced with \(y\) and vice-versa. We have achieved the same target state but the swap on a path edge is removed and replaced by a swap on a star edge, hence reducing the number of swaps on the path edge. Theorem 4.1: _Algorithm \(A_{b}\) computes an optimal swap sequence, i.e., a sorting sequence with the least possible number of swaps._  
Proof: We prove that our algorithm obtains an optimal swap sequence by applying induction on marker \(n\). The base case is just a star \(S\). Depending on the position of \(S_{min}\) and \(P_{max}\), we consider different cases and prove them individually. Moreover, for the general induction step, we prove that swaps performed by \(S_{min}\) and \(P_{max}\) are a part of an optimal swap sequence. Case (1): The initial position of \(S_{min}\) is any path vertex other than the center vertex. Let \(S^{\prime}_{opt}\) be the optimal swap sequence. Property 2 and Property 3 ensures that \(n\) will never encounter a star marker on the path and hence it will only swap path markers on its way home. Let \(d\) be the distance from the initial position of marker \(n\) to its home vertex \(H_{n}\). So, \(S^{\prime}_{opt}\) contains \(d\) swaps which involves marker \(n\). Let \(S_{i}\) be the swap that homes marker \(n\), therefore \(S_{1},S_{2},\ldots,S_{i}\) contain \(d\) swaps which includes marker \(n\) and \((i-d)\) swaps that do not include marker \(n\). Call this intermediate configuration \(T\). Create a separate swap sequence \(S_{opt}\) which homes \(n\) in first \(d\) swaps followed by \(i-d\) swaps that do not involve \(n\) and then carry on with rest of the swaps from \(S_{i+1},\ldots,S_{k}\).