Kurs:Algorithmen und Datenstrukturen/Vorlesung/Sortieren2 Rückblick




Rückblick und Ausblick

Bearbeiten

Die bisherigen Verfahren sortieren n Zahlen mit n*log b Vergleichen, zum Beispiel QuickSort im Durchschnittsfall. Die Sortierungen werden durch Vergleiche und Vergleich-Sortierung bestimmt. Wir haben gezeigt, dass n log n eine untere Schranke für Sortieralgorithmen die auf Vergleichen und Elementvergleichen basieren ist. Doch geht es auch besser? Auf den nächsten Seiten werden wir das verteilte Sortieren und das nicht vergleichsbasierte Sortieren kennenlernen.


Literatur

Bearbeiten

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 5.2.7 zu finden.