2003/12/23 by Krzysztof C. Kiwiel, Kiwiel, Krzysztof C. · 2 citations
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0312054
21 pages
arxiv created 2003/12/23 · arxiv updated 2009/12/01
We introduce several modifications of the partitioning schemes used in Hoare's quicksort and quickselect algorithms, including ternary schemes which identify keys less or greater than the pivot. We give estimates for the numbers of swaps made by each scheme. Our computational experiments indicate that ternary schemes allow quickselect to identify all keys equal to the selected key at little additional cost.