# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 5 Breakpoints-Based Approximation Algorithms
Now, we have to show that, after each of the, at most, four operations is applied, we have a \(\lambda\)-permutation as result. Observe that the absolute value of any element in \(R\) is greater than any element in \(S\). Since each \(\lambda\)-transposition puts elements of \(S\) closer to their correct positions by transposing them with greater elements (in their absolute values) of \(R\), we have a \(\lambda\)-permutation after each \(\lambda\)-operation applied. After all \(\lambda\)-transpositions are applied, the elements of \(S\) are at positions from \(i\) to \(i+k-j\), and the elements of \(R\) are at positions from \(i+k-j+1\) to \(k\), resulting in \(\pi\cdot\tau(i,j,k+1)\), which is a \(\lambda\)-permutation with at least \(b(\pi)-1\) breakpoints, as shown in Lemma 6. For a \(\lambda\)-permutation \(\pi\) with only increasing strips, the next lemma shows how to decrease the number of breakpoints in \(\pi\) using only \(\lambda\)-reversals, also assuring that all permutations generated in the process are \(\lambda\)-permutations. **Lemma 8**: _Let \(\pi\) be a \(\lambda\)-permutation. Let \(|\pi_{j}|=i\) be the smallest element out-of-place in \(\pi\). Suppose that \(\pi\) only has increasing strips and that \(\pi_{j}\) is in a strip \(S=(\pi_{j}\,\dots\,\pi_{k})\). It is always possible to obtain a \(\lambda\)-permutation \(\pi\cdot\tau(i,j,k+1)\) with, at most, \(b(\pi)-1\) breakpoints by applying, at most, \(5+\lambda-1\,\lambda\)-reversals such that all intermediary permutations are \(\lambda\)-permutations._  
Let \(R=(\pi_{i}\,\dots\,\pi_{j-1})\) be the segment that will be moved to the right in \(\tau(i,j,k+1)\). Note that \(|S|\leq\lambda-1\), by Lemma 2, and \(|R|\leq\lambda-1\), because \(\pi\) is a \(\lambda\)-permutation. The idea is to move elements from \(S\) to their correct positions by applying, at most, two sequences of pairs of \(\lambda\)-reversals, where each one puts, at most, \(\lfloor\lambda/2\rfloor\) elements of \(S\) in their correct positions at a time. In the first sequence of \(\lambda\)-reversals, there are two possibilities. If \(|S|\leq\lfloor\lambda/2\rfloor\), then the first operation of each pair reverses \(|S|\) elements contained in both \(S\) and \(R\). If \(|S|>\lfloor\lambda/2\rfloor\), then it reverses \(\lfloor\lambda/2\rfloor\) elements contained in both \(S\) and \(R\). In any case, the second operation of each pair reverses back the elements of \(R\) affected by the first one, in order to leave \(\pi\) with only increasing strips again (except for the elements of \(S\) which were affected by the first operation). After the sequence is applied, we have, at most, \(\lfloor\lambda/2\rfloor\) elements of \(S\) from positions \(i\) to \(i+\min(\lfloor\lambda/2\rfloor,|S|)\), and, maybe, they are in a decreasing strip. If this is the case, then one more \(\lambda\)-reversal has to be applied to put these elements in their correct places, by reversing such decreasing strip. The second sequence of \(\lambda\)-reversals puts the (at most) \(\lfloor\lambda/2\rfloor\) remaining elements of \(S\) in their correct positions, following the same idea, and, also, maybe one extra \(\lambda\)-reversal will be necessary after it is applied. Note that, if there are no remaining elements (in case of \(|S|\leq\lfloor\lambda/2\rfloor\)), this sequence is not necessary. The largest amount of operations needed in the process described above happens when we have \(\lfloor\lambda/2\rfloor+1\) elements in \(S\). Since \(|S|>\lfloor\lambda/2\rfloor\), our process starts by moving the first \(\lfloor\lambda/2\rfloor\) elements of \(S\) to their correct positions. Observe that, for each pair of reversals applied in the first sequence, one of them moves \(\lfloor\lambda/2\rfloor\) elements \(\lfloor\lambda/2\rfloor\) positions to the left (except, maybe, by the last pair), and then the other one reverses again the elements of \(R\) affected by the first reversal.