| 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.