SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-40623
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4062/


Smoothsort's behavior on presorted sequences

Hertel, Stefan

Quelle: (1982) Saarbr├╝cken, 1982
pdf-Format:
Dokument 1.pdf (2.277 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Institut: Fachrichtung 6.2 - Informatik
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

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English