Paper by Erik D. Demaine
- Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, and J. Ian Munro, “Fun-Sort”, in Proceedings of the 2nd International Conference on Fun with Algorithms (FUN 2001), Isola d'Elba, Italy, May 29–31, 2001, pages 15–26.
In this paper we study greedy in-place sorting algorithms which miraculously
happen to work in reasonable time. Dumb-Sort which repeatedly compares all
possible pairs of array cells sorts n elements in
n − 1 cycles, or time O(n3).
Not-So-Dumb-Sort, which only tests adjacent cells, also sorts in
n − 1 cycles, or in time O(n2).
Guess-Sort, a randomized version of Dumb-Sort, runs in expected time
O(n2 log n). And Fun-Sort, an
in-place variant of Insertion-Sort that performs repeated insertions by binary
search into an initially unsorted array, sorts in time
O(n2 log n).
- The paper is 12 pages.
- The paper is available in PostScript (215k) and gzipped PostScript (107k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- FunSort_DAM (Fun-Sort—or the Chaos of Unordered Binary Search)
- FunSort_TR2001 (Fun-Sort)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated February 10, 2020 by