|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/706
|
| Title: | Fun-sort |
| Authors: | Biedl, Therese
Chan, Timothy
Demaine, Erik D.
Fleischer, Rudolf H.
Golin, Mordecai J.
Munro, J. Ian |
| Keywords: | Dumb-Sort
Not-So-Dumb-Sort
Guess-Sort
Insertion-Sort |
| Issue Date: | 20-Feb-2001 |
| Series/Report no.: | HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2001-03 |
| Abstract: | 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). |
| URI: | http://hdl.handle.net/1783.1/706 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 200103.pdf | | 237Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
