# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 5 Breakpoints-Based Approximation Algorithms
Besides that, by the definition of \(\lambda\)-permutations, the elements of \(S\) are, at most, \(\lambda-1\) positions away from their correct positions, and, so, at most, 2 pairs of reversals are needed to put them at position \(i\). As we have told before, maybe such elements of \(S\) ended up in reversed order and, in order to fix it, one more reversal is needed. Hence, we already have a total of, at most, 5 reversals applied. To move the remaining element of \(S\) to its correct position, all the \(\lambda\)-reversals of the second sequence will have size 2 (note that, in this case, we do not need the second operation of each pair), which means such element will be moved only 1 position to the left per operation, giving an extra amount of \(\lambda-1\)\(\lambda\)-reversals. Therefore, the number of \(\lambda\)-reversals to move \(S\) to its correct position is, at most, \(5+\lambda-1\). Now, we have to show that, after applying each operation, we have a \(\lambda\)-permutation as result and, after the last operation is applied, we have \(\pi\cdot\tau(i,j,k+1)\). Observe that any element in \(R\) is greater than any element in \(S\). Then, since the first operation of each pair moves elements of \(R\) to the right and elements of \(S\) to the left, all elements affected will be closer to their correct positions, resulting in a \(\lambda\)-permutation. The second operation of each pair reverses elements of \(R\) to ascending order again, so it also results in a \(\lambda\)-permutation. After both sequences of \(\lambda\)-reversals are applied, all elements of \(S\) are at positions from \(i\) to \(i+k-j\) and all elements of \(R\) are at positions from \(i+k-1\) to \(k\), resulting in \(\pi\cdot\tau(i,j,k+1)\), which is a \(\lambda\)-permutation with at least one less breakpoint than \(\pi\), as shown in Lemma 6. Lemma 9 shows how to decrease the number of breakpoints of a \(\lambda\)-permutation \(\pi\), considering that the smallest element out-of-place of \(\pi\) is in a decreasing strip. Since Lemma 8 deals with the case where \(\pi\) has no decreasing strips, we can use these two lemmas together to develop an algorithm to sort a \(\lambda\)-permutation \(\pi\) using only \(\lambda\)-reversals. **Lemma 9**. : _Let \(|\pi_{k}|=i\) be the smallest element out-of-place in a \(\lambda\)-permutation \(\pi\). Suppose that \(\pi_{k}\) is in a decreasing strip \(S=(\pi_{j}\,\dots\,\pi_{k})\). It is always possible to obtain a \(\lambda\)-permutation with, at most, \(b(\pi)-1\) breakpoints by applying, at most, one \(\lambda\)-transposition and one \(\lambda\)-reversal._  
Proof. : When \(j=i\), one reversal \(\rho(j,k)\) put elements of \(S\) in their correct positions. It is easy to see that \(\pi\cdot\rho(j,k)\) is a \(\lambda\)-permutation and, since \(|S|=k-j+1\leq\lambda-1\) by Lemma 2, we have that \(\rho(j,k)\) is a \(\lambda\)-reversal. Now, assume \(j>i\). Note that, in this case, we have the three breakpoints \((\pi_{i-1},\pi_{i})\), \((\pi_{j},\pi_{j+1})\), and \((\pi_{k-1},\pi_{k})\), where the first one is because \(\pi_{i-1}=|\pi_{k}|-1=i-1\) and \(|\pi_{i}|>i=|\pi_{k}|\), and the second and third ones are because the strip's start and strip's end are at positions \(k\) and \(j\), respectively. Thus, we can apply the \(\lambda\)-transposition \(\tau(i,j,k+1)\) followed by the \(\lambda\)-reversal \(\rho(i,i+(k-j))\) to obtain \(b(\pi\cdot\tau(i,j,k+1)\cdot\rho(i,i+(k-j)))\leq b(\pi)-1\), since a \(\lambda\)-transposition can add, at most, three breakpoints but we already had \((\pi_{i-1},\pi_{i})\), \((\pi_{j-1},\pi_{j})\), and \((\pi_{k},\pi_{k+1})\), and the second \(\lambda\)-reversal can add, at most, two breakpoints, but we already had \((\pi_{i-1},\pi_{j})\) and \((\pi_{k},\pi_{i})\) and we removed the first one, since all elements of \(S\) will be in their correct positions in \(\pi\cdot\tau(i,j,k+1)\cdot\rho(i,i+(k-j))\). Now, we have to show that, after each operation is applied, we have a \(\lambda\)-permutation as result.