Article ID: | iaor2014939 |
Volume: | 69 |
Issue: | 4 |
Start Page Number: | 958 |
End Page Number: | 973 |
Publication Date: | Aug 2014 |
Journal: | Algorithmica |
Authors: | Roura Salvador, Frias Leonor |
Keywords: | datamining, optimization |
We present multikey quickselect: an efficient, in‐place, easy‐to‐implement algorithm for the selection problem for strings. We analyze its expected cost under a uniform model, measured as the number of character comparisons and pointer swaps, depending on the alphabet cardinality. From the analysis, we derive a binary variant of the algorithm, which is more efficient when the range of values for the alphabet is known. This variant can also be applied to multikey quicksort.