# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 6 Experimental Results  
In order to analyze how the proposed algorithms work from a practical perspective, we have implemented the inversions-based (Theorems 2 and 3) and the breakpoints-based (Theorems 4-6) greedy algorithms. We can also achieve an approximation factor of \(O(\lambda^{2})\) with algorithms that always apply an operation of size \(2\) according to Lemma 3, for unsigned permutations, or Lemma 5,for signed permutations. There exists a way to implement such algorithms so that they have time complexity of \(O(n\log n)\)[25]. We also implemented these algorithms, which we named super short algorithms, for comparison purposes. The difference between the super short algorithms and the inversions-based algorithms from Theorems 2 and 3 is that the super short algorithms only use operations of size 2, while the algorithms from Theorems 2 and 3 use, at each iteration, the operation that most decrease the number of inversions, which can have size, at most, \(\lambda\). We performed experiments considering a total of 1000 signed and unsigned \(\lambda\)-permutations, with size equal to 100 and values of \(\lambda\in\{5,10,15,\ldots,100\}\), as input for the algorithms. The considered \(\lambda\)-permutations were generated in two different ways: (i) totally random, and (ii) by applying 20 random \(\lambda\)-operations (according to the rearrangement model of each problem) over the identity. We reinforce that all generated permutations in both cases, including the intermediary ones of case (ii), are \(\lambda\)-permutations. For (i), the \(\lambda\)-permutations tend to have a high amount of breakpoints, and for (ii) they tend to have a high amount of strips and, moreover, we know the distance is, at most, 20. Then, we compared the results according to the average and maximum approximation factors obtained for all permutations. For each permutation, we calculated the approximation factor by dividing the size of the sorting sequence by the maximum value of lower bound between the ones shown in Lemma 1 and Fact 1. We show the results for totally random \(\lambda\)-permutations in Figures  
Figure 2: Average and maximum approximation factors of the algorithms for Sorting Unsigned \(\lambda\)-Permutations by \(\lambda\)-Operations, with totally random \(\lambda\)-permutations of size 100 as inputs. Note that a logarithmic scale is used in the y-axis of each graph. Figure 4: _Cont_. Figure 3: Average and maximum approximation factors of the algorithms for Sorting Signed \(\lambda\)-Permutations by \(\lambda\)-Operations, with random \(\lambda\)-permutations generated from \(\iota\) of size 100 as inputs. Note that a logarithmic scale is used in the y-axis of each graph. Even though the inversions-based and the super short algorithms have the same theoretical approximation factor, the experiments show that the inversions-based algorithms are much better in practice. Hence, for the rest of this analysis, we only compare the results of the inversions-based and breakpoints-based algorithms. Considering the results for totally random \(\lambda\)-permutations, we observed that the maximum approximation factors for sorting unsigned \(\lambda\)-permutations problems were 5.38 and 7.04 for \(\lambda\)-reversals, 2.91 and 3.06 for \(\lambda\)-transpositions, and 3.00 and 3.15 for when both \(\lambda\)-operations are allowed, considering the breakpoints-based and the inversions-based algorithms, respectively. For the sorting signed \(\lambda\)-permutations problems, the maximum approximation factors were 7.78 and 7.54 for \(\lambda\)-reversals and 4.74 and 5.21 for when both \(\lambda\)-operations are allowed, considering the breakpoints-based and the inversions-based algorithms, respectively.