Sorting by Reversals Demo

Goal:

The goal is to sort a permutation array to the identity permutation only by reversing subarrays of it in the minimal number of reversals.

Initialization:

Choose the size of an array, enter it in the box at the lower left corner, then click on [GO]. A random array of the chosen size will be displayed.

Sorting:

Click on two of the boxes of the array. The subarray between and including them will be reversed.

Counter:

Indicates the number of reversals.

References

• [BHK02] P. Berman, S. Hannenhalli, and M. Karpinski,
  1.375-Approximation Algorithm for Sorting by Reversals,
  Proc. 10th ESA (2002), LNCS Vol. 2461, pp. 200-210, 2002.


• [BK99] P. Berman and M. Karpinski,
  On Some Tighter Inapproximability Results,
  Proc. 26th ICALP (1999), LNCS Vol. 1644, pp. 200-209, 1999.


• [BP96] V. Bafna and P.A. Pevzner,