Eingang zum Volltext in SciDok
Lizenz
Report (Bericht) zugänglich unter
Smoothsort's behavior on presorted sequences
URN: urn:nbn:de:bsz:291-scidok-40623
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4062/
Quelle:
(1982) Saarbrücken, 1982
pdf-Format:
Dokument 1.pdf (2.277 KB)
Institut:
DDC-Sachgruppe:
Informatik
Dokumentart:
Report (Bericht)
Schriftenreihe:
Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Bandnummer:
1982/11
Sprache:
Englisch
Erstellungsjahr:
1982
Publikationsdatum:
01.08.2011
Kurzfassung auf Englisch:
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.
Lizenz:
Standard-Veröffentlichungsvertrag