Title :
An adaptive generic sorting algorithm that uses variable partitioning
Author :
Estivill-Castro, V. ; Wood, D.
Author_Institution :
LANIA, Veracruz, Mexico
Abstract :
Presents a generic sorting algorithm that uses divide-and-conquer in which the number of subproblems depends on the disorder of the input and for which we can establish adaptivity with respect to an abstract measure. We present applications of this generic algorithm obtaining optimal adaptivity for several specific measures of disorder. Moreover, we define a randomized version of our generic algorithm that simplifies implementations
Keywords :
algorithm theory; sorting; abstract measure; adaptive generic sorting algorithm; divide-and-conquer method; input disorder; optimal adaptivity; randomized version; subproblems; variable partitioning; Adaptive algorithm; Algorithm design and analysis; Computer science; Content addressable storage; Length measurement; Machinery; Particle measurements; Partitioning algorithms; Protocols; Sorting;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315411
