TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Übungen SS09/Beispiel 11

1. Sie haben eine nicht sortierte, einfach verkette lineare Liste. Welches Sortierverfahren verwenden Sie, um die Liste zu sortieren? Begründen Sie Ihre Antwort.
2. 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

• Insertion-Sort
• Selection-Sort
• Merge-Sort
• Quick-Sort
• Heap-Sort

Lösung 1

• 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

• Insertion-Sort

Gesamte Laufzeit im Worst-Case macht ihn zum Verlierer

• Selection-Sort

Ebenfalls zu langsam im Vergleich, da Anzahl der Schlüsselvergleiche immer $n^{2}$

• 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