Abstract:
|
In this paper we introduce Multikey Quickselect: an efficient, in-place, and easy to implement algorithm for the selection problem for strings. We present several variants of our basic algorithm, which apply to two different flavors of the selection problem. Also, we analyze the cost of the main variants, measured as the expected number of character comparisons and elements swaps. Some of the enhancements presented in this paper apply to Multikey Quicksort as well. |