Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26093
Titel: Smoothsort's behavior on presorted sequences
Verfasser: Hertel, Stefan
Sprache: Englisch
Erscheinungsjahr: 1982
Quelle: Saarbrücken, 1982
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: In [5], Mehlhorn presented an algorithm for sorting nearly sorted sequences of length n in time 0(n(1+log(F/n))) where F is the number of initial inversions. More recently, Dijkstra[3] presented a new algorithm for sorting in situ. Without giving much evidence of it, he claims that his algorithm works well on nearly sorted sequences. In this note we show that smoothsort compares unfavorably to Mehlhorn's algorithm. We present a sequence of length n with O(nlogn) inversions which forces smoothsort to use time Omega(nlog n), contrasting to the time O(nloglogn) Mehlhorn's algorithm would need.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-40623
hdl:20.500.11880/26149
http://dx.doi.org/10.22028/D291-26093
Schriftenreihe: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Band: 1982/11
SciDok-Publikation: 1-Aug-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1982_11.pdf2,28 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.