File DidacticSorts.h

↰ Parent directory (ADS/sort)

Three sorts that are slow on purpose, beyond the book, as examples of the analysis of recurrences and of the expected time:

Definition (ADS/sort/DidacticSorts.h)

Detailed Description

  • stoogeSort() sorts the first two thirds, the last two thirds and the first two thirds again, :math:` T( n ) = 3 T( 2 n / 3 ) + O( 1 ) , i.e., :math: Theta( n^{log_{1.5} 3} ) = O( n^{2.71} ) ` by the master theorem [see File MasterTheorem.h];

  • slowSort() of Broder and Stolfi (multiply and surrender): the maximum of the two halves, sorted recursively, goes to the end and the rest is sorted again, :math:` T( n ) = 2 T( n / 2 ) + T( n - 1 ) + 1 `, which is not even polynomial;

  • bogoSort() shuffles the vector until it is sorted, n! / ( number of sorted orders ) shuffles expected, each O( n ).

The contracts [see File Contract.h]: bogoSort() needs n <= 10, so that it ends in a reasonable time; each sort ends with the same items sorted, an audit. The functions are defined in DidacticSorts.tpp.

    1. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009, problem 7-3 (stooge sort)

  1. Broder, J. Stolfi, Pessimal algorithms and simplexity analysis, ACM SIGACT News 16(3), 49-53, 1984, doi:10.1145/990534.990536

  1. Gruber, M. Holzer, O. Ruepp, Sorting the slow way: an analysis of perversely awful randomized sorting algorithms, Proceedings of FUN 2007, LNCS 4475, 183-197, 2007

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions