Bachelorarbeit BCLR-2019-110

Bibliograph.
Daten
Obst, Julian: Experimentelle Bestimmung vergleichsoptimaler Sortieralgorithmen.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 110 (2019).
43 Seiten, deutsch.
Kurzfassung

Die gängigsten Sortierverfahren sortieren Mengen, indem sie zwei Elemente miteinander vergleichen und damit Schritt für Schritt eine Ordnung aufbauen. Es stellt sich die Frage, was die minimale Anzahl an Vergleichen ist, die benötigt wird, um eine beliebige Permutation einer Menge zu sortieren. Das zentrale Ziel dieser Arbeit ist es, die theoretischen Grundlagen zur Bestimmung vergleichsoptimaler Sortieralgorithmen zu erläutern und die Anzahl der Vergleiche von solchen Algorithmen zu bestimmen. Dabei werden auch die praktischen Ansätze besprochen, die benutzt wurden, um einen Algorithmus zu erstellen, der dieses Problem lösen soll. In diesem Zusammenhang werden die Aspekte der Implementierung dieses Algorithmus beleuchtet. Vor allem werden in diesem Punkt aber auch Optimierungen beschrieben, die helfen sollen, die Laufzeit zu verkürzen. Für n = 12, 13 konnten bekannte Ergebnisse bestätigt werden.

Volltext und
andere Links
Volltext
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerDiekert, Prof. Volker; Weiß, Dr. Armin
Eingabedatum9. Juni 2020
   Publ. Informatik