TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 11
- Sie haben eine nicht sortierte, einfach verkette lineare Liste. Welches Sortierverfahren verwenden Sie, um die Liste zu sortieren? Begründen Sie Ihre Antwort.
- Sie haben eine nicht sortierte, doppelt verkettete lineare Liste. Welches Sortierverfahren verwenden Sie in diesem Fall, um die Liste zu sortieren? Begründen sie Ihre Antwort.
Mögliche Sortierverfahren[Bearbeiten | Quelltext bearbeiten]
- Insertion-Sort
- Selection-Sort
- Merge-Sort
- Quick-Sort
- Heap-Sort
Lösung 1[Bearbeiten | Quelltext bearbeiten]
- Insertion-Sort ist der optimale Algorithmus
Da man die Liste schnell umstrukturieren kann, indem man drei Pointer verändert. (Der Nachteil - das Platzmachen für den eingefügten Wert - entfällt, und wird durch eine Konstante 3 (Zeiger) ersetzt)
- Selection-Sort
Nützt den Vorteil der verketteten Liste nicht, also ist ähnlich schlecht wie bei einer linearen Liste
- Merge-Sort
Der Schritt zurück, der hier notwendig wäre, bzw. das Umdrehen der Werte im Merge ist, da es eine einfach verkette Liste ist nicht möglich, sprich er wird sehr ineffizient
- Quick-Sort
Das selbe wie Merge-Sort (Schritte zurück nicht möglich, daher ungünstig)
- Heap-Sort
Ebenfalls das selbe: Die Zugriffe auf das Element 2n und 2n+1, ist hier nicht direkt Möglich, sondern man muss sich umständlich "durchhanteln"
Lösung 2[Bearbeiten | Quelltext bearbeiten]
- Insertion-Sort
Gesamte Laufzeit im Worst-Case macht ihn zum Verlierer
- Selection-Sort
Ebenfalls zu langsam im Vergleich, da Anzahl der Schlüsselvergleiche immer
- Merge-Sort
Nicht so gut wie Quick-Sort, da man zwar einen Schritt zurück machen könnte, jedoch n zusätzlichen Speicher braucht.
- Quick-Sort
"In der Praxis der beste Algorithmus" - sehr effizienter Algorithmus, da man schnell einen Knoten nach vorne und nach hinten springen kann. Und das Vertauschen ist ebenfalls leicht (durch Pointer Veränderung)
- Heap-Sort
So wie in Lösung 1 ist der Zugriff auf die Elemente 2n und 2n+1 in einer doppelt verketten Liste nicht so einfach