Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2019/20 / Oberseminar / Stephan Barth: Ein neuer Sortieralgorithmus und wieso wir einen weiteren brauchen


Inhaltsbereich

Stephan Barth: Ein neuer Sortieralgorithmus und wieso wir einen weiteren brauchen

Oberseminarvortrag von Stephan Barth über Ein neuer Sortieralgorithmus und wieso wir einen weiteren brauchen
Wann 14:15 16:00 10.01.2020
von bis
Wo Raum L109, Oettingenstr. 67
Termin übernehmen vCal
iCal

Es spricht Stephan Barth über:
Ein neuer Sortieralgorithmus und wieso wir einen weiteren brauchen

Abstract:
Sortieralgorithmen gelten gemeinhin als ein gelöstes Problem:
Sortieren in O(n log n) ist optimal mit bekannten und nicht zu
komplizierten Lösungen.

Dennoch gibt es für Sortieralgorithmen noch Verbesserungspotential:
Einige Sortieralgorithmen eignen sich für bestimmte Aufgaben besser
als andere, beispielsweise gibt es Timsort, eine Variante von
Mergesort, welche teilweise vorsortierte Listen für eine schnellere
Sortierung weiterverwenden kann; zudem partial Quicksort/Quickselect,
eine Variante von Quicksort, welche effizient das k-kleinste Element
finden kann, ohne die ganze Liste sortieren zu müssen.

Um einen Sortieralgorithmus zu erhalten, welcher in einer Reihe von
Spezialfällen Vorteile gegenüber anderen Sortieralgorithmen hat,
kombinieren wir Konzepte aus Quicksort, Mergesort, Bucketsort und
Heaps zu einem neuen Sortieralgorithmus: Platypussort.

Dadurch, dass Platypussort sich in vielen Anwedungsfällen besser
verhält, als verbreitete Algorithmen, aber dennoch die gleiche
worst-case-Laufzeit O(n log n) hat, hätte er Vorteile als
Standardsortieralgorithmus. Diese Vorteile erkauft er sich allerdings
nicht zuletzt durch einen deutlich höheren Implementierungsaufwand.

Artikelaktionen


Funktionsleiste