# Optimal Algorithms for Sorting Permutations with Brooms
## 3 Sorting Permutations with a Single Broom
### Correctness of \(A_{b}\)
Homing marker \(n\) does not alter the relative order of the remaining markers. Clearly, we have attained the same configuration state as in \(T\), implying \(S_{opt}\) is an optimal swap sequence which is generated by our algorithm \(A_{b}\). Consider \(S^{\prime}\) be an optimal swap sequence which brings \(n\) to the center vertex. Observe that \(n\) can be placed on center in exactly \(d-1\) swaps, where \(d\) is the distance of \(n\) from its home vertex \(H_{n}\) on the star leaf. Let \(S_{c}\) be the swap in \(S^{\prime}=S_{1},S_{2},\ldots,S_{c}\) that places marker \(n\) on the center and \(T\) be the intermediate configuration of the markers after \(S_{c}\). Create a swap sequence \(S\) that homes the marker \(n\) first in \(d-1\) swaps and carries out the rest of the \(c-(k-1)\) swaps, which does not include \(n\). Clearly, you will get the same resulting configuration as of \(T\) with the same number of swaps. Hence, \(S\) is an optimal swap sequence. Now, call \(S_{h}\) the swap that homes \(n\) from the center vertex by swapping it with an arbitrary marker \(t\) residing on \(H_{n}\). Aforementioned discussion assumes that no swaps which involve star edges occur before \(S_{h}\). Otherwise, when \(n\) is initially placed on the center vertex or arrives at the center with the swap \(S_{c}\), it suffices to show that \(S_{opt}\) is optimal which does not alter the position of \(n\) before the swap \(S_{h}\). We do some modifications in \(S_{opt}\) to make this true. Split the subsequence \(S_{1},S_{2},\ldots,S_{h-1}\) into \(S_{path}\) and \(S_{star}\), where the subsequence \(S_{path}\) contains the swaps that occur on path edges and the subsequence \(S_{star}\) contains the swaps that occur on star edges. Note that \(S_{path}\) does not move marker \(n\) from its position and \(S_{star}\) always places \(n\) back to the center. We can rearrange this subsequence containing \(S_{star}\) and \(S_{path}\) as there are no star markers moving towards the path and vice versa as mentioned in Property 5. After \(S_{path}\), carry out the swap \(S_{h}\) and then perform the swaps in \(S_{star}\) but with \(t\) and \(n\) exchanged. This results in the same placement of markers with no change in the swap count on the star and path. Hence, \(S_{opt}\) is same as the optimal sequence generated by our algorithm \(A_{b}\). Case (2): After Step 1 of \(A_{b}\), it is important to observe that we are now only left with path markers as all the star markers are either homed or residing on star nodes (will be homed in Step 3). So, lets consider marker \(n=P_{max}\) is on a path vertex, except the center vertex. According to the property proved before, \(P_{max}\) will always move to the right, swapping the lesser value marker to the left. Let \(S\) be the swap sequence which contains swap moves for homing \(P_{max}\). Consider \(S_{h}\) to be the swap which slots \(P_{max}\) in its home and \(T\) be the configuration at that instance. Considering distance \(d\) between \(P_{max}\) and its home, we can say \(S_{1}\ldots S_{h}\) will have \(d\) swaps involving \(P_{max}\) and \((i-d)\) not involving \(P_{max}\) (say \(S^{\prime}\) be that swap sequence). To modify \(S\), we first make \(d\) swap moves which involve \(P_{max}\), followed by \(S^{\prime}\) and then \(S_{i+1}\ldots S_{final}\), call this swap sequence \(S_{o}\). It is interesting to observe that initial \(d\) swap moves will not change the relative order of the rest of the path markers, post which, \(S^{\prime}\) swap moves can be performed, ultimately resulting in the same configuration \(T\); hence \(S_{o}\) is optimal. Now, suppose \(n=P_{max}\) is on the center vertex. Let \(S_{P}\) be the swap that marker \(n\) on the first path edge \(e=(v_{k+1},v_{k+2})\) with an arbitrary marker \(t\). If we assume there are no swaps before \(S_{P}\), we can just prove it with the above mentioned discussion in Case 2. Else, it suffices to show that \(S_{opt}\) is optimal and does not alter the position of \(n\) before \(S_{p}\). We modify \(S_{opt}\) to make this true.