Folien zur Vorlesung Sortierverfahren

Die hier frei verfügbare Foliensammlung stammt aus der gleichnamigen Master-Veranstaltung im Sommersemester 2014. Das zugehörige Skript (in Englisch) kann als PDF heruntergeladen werden von der Universität Turku (Lutz M. Wegner, Sorting – The Turku Lectures, Lecture Notes in Computing 2014, Univ. of Turku, Finland, http://tucs.fi/publications/attachment.php?fname=bWegner_LutzMx14a.full.pdf). Das überarbeitete Material geht auf eine dort im Jahre 1987 gehaltene Gastvorlesung zurück. Betrachtet werden Varianten von Quicksort und Heapsort, speziell bei Quicksort solche für Multimengen und Vorsortierung, sowohl für verkettete Listen als auch für Datenstrukturen mit Direktzugriff. Neben dem Standardheapsort werden die Floydverbesserung und Dijkstras Smoothsort vorgestellt. Eine Netzwerkvariante und zwei Externspeicherverfahren auf Basis von Quicksort und Heapsort werden untersucht. Der Stand der Technik bei den stabilen, in-situ Verfahren wird skizziert. Der Stoff eignet sich für eine Vorlesung mit angegliederten Projektübungen, in denen Studierende selbstständig Algorithmen, die als Pseudo-Code vorgegeben sind, in effizienten, lauffähigen Java-Code umsetzen und in einer Laufzeitbibliothek mit vorgegebenen Testdaten messen.