Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
In-Place Sorting
verfasst von : Viliam Geffert, Jozef Gajdoš
Erschienen in: SOFSEM 2011: Theory and Practice of Computer Science
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 present an algorithm for asymptotically efficient sorting. Our algorithm sorts the given array
$\mathcal A$
by the use of
$n\!\cdot\!\lg n + O(n\!\cdot\!\lg\lg n)$
comparisons and
O
(
n
) element moves. Moreover, this algorithm works in-place, using only a constant auxiliary workspace. This shrinks the gap between the known information-theoretic lower bound and the existing algorithms to
$O(n\!\cdot\!\lg\lg n)$
comparisons, even if we require the algorithm to use only a constant auxiliary memory and a linear number of moves.