Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Multikey quickselect

Autor
Frias, L.; Roura, S.
Tipus d'activitat
Article en revista
Revista
Algorithmica
Data de publicació
2014-08-01
Volum
69
Número
4
Pàgina inicial
958
Pàgina final
973
DOI
https://doi.org/10.1007/s00453-013-9775-2 Obrir en finestra nova
URL
http://link.springer.com/article/10.1007%2Fs00453-013-9775-2 Obrir en finestra nova
Resum
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.
Paraules clau
Analysis of algorithms, Average-case, Divide-and-conquer, Partition, QUICKSORT, SORT, STRINGS, Selection, Strings
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants