# Optimal Algorithms for Sorting Permutations with Brooms
## 3 Sorting Permutations with a Single Broom
### Correctness of \(A_{b}\)  
In this section, we prove that \(A_{b}\) finds an optimal swap sequence, \(S_{opt}\), which always follows some interesting properties. To show that, \(S_{opt}\) is optimal, we first prove that these properties hold for a given marker on a broom and then apply induction on \(n\). **Lemma 1**. : _An optimal path sequence \(S_{opt}\) will obey following properties:_  
1. A pair of markers swap at most once. **Proof. ** We prove it using contradiction. Suppose the swap sequence \(S=S_{1},S_{2},S_{3}\ldots S_{s}\), contains the swap of \((x,y)\) twice at \(S_{i}\) and \(S_{j}\). Modify \(S\) by deleting \(S_{i}\) and \(S_{j}\). Then, for each swap \(S_{k}\) where \(i<k<j\), replace \(x\) with \(y\) and vice-versa. Resulting swap sequence is shorter and achieves the same results. 2. Star markers that enter the star from path do so in the increasing order of their distance from center. **Proof. ** Consider two star markers \(x\) and \(y\) residing on the path. Assume \(x\) and \(y\) are at a distance \(d\) and \(d+c\) respectively from their home. Let S be the swap sequence containing the swap \(S_{i}\) which swaps \(y\) and \(x\) on the path. Marker \(y\) will be honed after a swap with the marker residing on its home \(H_{y}\), call this swap \(S_{j}\) where \(j>i\). Similarly \(x\) will be honed after a final swap \(S_{k}\) with \(H_{x}\) where \(k>j\). Call this  
Figure 3: Comparison of algorithm \(A_{b}\) with [PERSON]’s and [PERSON]’s algorithms. (**a**) \(S_{min}=3\), Swaps = 2; \(S_{min}=4\), Swaps = 3. (**b**) Maximum valued path token(\(P_{max}\)) = 9, Swaps = 3; \(P_{max}=8\), Swaps = 3. (**c**) Maximum valued token(\(T_{max}\)) = 9, Swaps = 3; \(T_{max}=8\), Star tokens = [3], Swaps = 4. (**d**) \(S_{min}=5\), Swaps = 1; \(S_{min}=2\), Swaps = 4. (**e**) \(P_{max}=7\), centered star chain = {4,5,3,7}, Swaps = 4. (**f**) \(T_{max}=7\), Star tokens = [4,5], Swaps = 3. (**g**)\(S_{min}=1\), Swaps = 1; \(P_{max}=8\), Swaps = 1, Total Swaps = 12. (**h**) \(P_{max}\) = 6, centered star chain = {2,1,6}, Swaps = 2, Total Swaps = 12. (**i**) \(T_{max}=6\), Star tokens = [2,1], Swaps = 2, Total Swaps = 12.  
intermediate configuration of markers as \(S^{\prime}\). We show how \(S\) can be modified in order to obtain an optimal sequence. To modify \(S\), omit \(S_{i}\) and carry out further swaps with \(x\) & \(y\) and \(H_{x}\) & \(H_{y}\) exchanged, until the swap \(S_{k}\). Observe that we have obtained the same marker configuration as in \(S^{\prime}\) but with fewer swaps. 3. Two star markers will never swap on a path edge. Proof. : Let us take \(x\) and \(y\) to be the star markers that swap on the path edge in \(S\). We show how \(S\) can be modified to obtain a swap sequence with a lesser number of swaps on the path. After the swap of \(x\) and \(y\) in \(S\), at some point of time, both \(x\) and \(y\) will get into the star. Let \(S^{\prime}\) be a sub sequence of \(S\), where \(y\) resides on a star leaf and \(x\) on the center node. To modify \(S\), remove the swap of \(x\) and \(y\) and replace \(x\) with \(y\) and vice versa for the following swaps. Iterate this till the point \(S^{\prime}\) is reached in \(S\) and add a swap of \(x\) and \(y\). We have achieved the same target state, but a swap carried out on the path is removed and compensated by adding an additional swap in the star. To illustrate the same, consider the swap sequence \(S=(1,2),(2,6),(2,3),(1,6),(1,3),\)\((1,4)\). Note that \(S^{\prime}=(1,2),(2,6),(2,3),(1,6),(1,3)\), where we have 2 at star leaf (say \(x\)) and 1 at the center (say \(y\)). If we omit the swap move \((1,2)\) and exchange \(x=1\), \(y=2\) we get the modified swap sequence as \((1,6),(1,3),(2,6),(2,3)\) (refer Figure 4). Followed by a swap move of \(x\) and \(y\) we achieve the same configuration as \(S^{\prime}\) but the swap of \(x\) and \(y\) on path edge is replaced by a swap on star edge, resulting in lesser swaps on path edges. 4.