TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 10
Welche in der Vorlesung behandelten Sortierverfahren eignen sich am Besten für die unten angeführten Fälle. Begründen Sie ihre Antwort.
(a) Eine beliebige Folge soll absteigend sortiert werden.
(b) Auf einem Abschleppplatz sollen Autos, aufsteigend nach ihrer Nummerntagel, umgparkt werden.
(c) In eine bereits aufsteigend sortierte Folg wird ein beliebig großes Element am Ende angehängt. Die neu entstandene Folge soll nun erneut aufsteigend sortiert werden.
(d) Eine beliebig große Anzahl an Rechnungen, die jeweils mit einem Datum und einer 4-stelligen Rechnungsnummer der Form YYYYMMDDRRRR versehen sind, soll sortiert werden.
Beispiel (a)[Bearbeiten | Quelltext bearbeiten]
Heapsort - Da es eine beliebige Folge ist könnte es bei jedem anderen Verfahren zu einem Worst-Case kommen, welcher sicher eine größere Laufzeit hat als Heapsort.
Beispiel (b)[Bearbeiten | Quelltext bearbeiten]
Selectionsort - Da hier sicher die "Datensatzbewegungen" das größte Problem darstellt, sollte man hier das "bewegungsarme" Selectionsort vorziehen.
Beispiel (c)[Bearbeiten | Quelltext bearbeiten]
Insertionsort - Da schon eine sortierte Folge vorliegt, muss man das neue Element nur mehr einordnen und alle Zahlen nach der eben eingefügt nach hinten rücken lassen. Dies hätte eine ungefähre Laufzeit von (n).
Beispiel (d)[Bearbeiten | Quelltext bearbeiten]
Bucketsort - Da man eine konstante Länge der Schlüssel hat, eignet sich hier Bucketsort am besten, mit einer linearen Laufzeit.