File CycleSort.h

↰ Parent directory (ADS/sort)

Two sorts that minimize an operation other than the comparison, beyond the book:

Definition (ADS/sort/CycleSort.h)

Detailed Description

  • cycleSort() of Haddon writes each item once into its final place, found by counting the items smaller than it, and follows the cycle of the permutation that the item displaces: at most n writes, the least possible, at the price of :math:` Theta( n^2 ) ` comparisons, which suits a memory whose writes are dear (e.g., flash); not stable;

  • pancakeSort() sorts by reversals of prefixes (flips) only: the largest item of the unsorted prefix is flipped to the front and then to the end of the prefix, at most 2 n - 3 flips, while Gates and Papadimitriou proved that ( 5 n + 5 ) / 3 always suffice and that 17 n / 16 may be needed.

The contracts [see File Contract.h]: each sort ends with the same items sorted, an audit; cycleSort() makes at most n writes and pancakeSort() at most max( 0 , 2 n - 3 ) flips. The functions are defined in CycleSort.tpp.

    1. Haddon, Cycle-sort: a linear sorting method, The Computer Journal 33(4), 365-367, 1990, doi:10.1093/comjnl/33.4.365

    1. Gates, C. H. Papadimitriou, Bounds for sorting by prefix reversal, Discrete Mathematics 27(1), 47-57, 1979, doi:10.1016/0012-365X(79)90068-2

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions