Multikey Quickselect

Multikey Quickselect

0.00 Avg rating0 Votes
Article ID: iaor2014939
Volume: 69
Issue: 4
Start Page Number: 958
End Page Number: 973
Publication Date: Aug 2014
Journal: Algorithmica
Authors: ,
Keywords: datamining, optimization
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.