2005 | OriginalPaper | Buchkapitel
Optimal In-place Sorting of Vectors and Records
verfasst von : Gianni Franceschini, Roberto Grossi
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length,
k
, is not a constant. We present the first algorithm for lexicographically sorting
n
keys in
O
(
nk
+
n
log
n
) time using
O
(1) auxiliary data locations, which is
simultaneously
optimal in time
and
space.