Sortieren

Question 1

Sortierverfahren - Definition

Answer 1

Algorithmus, der dazu dient, eine Liste von Element zu sortieren

Question 2

Klassifikation von Sortierverfahren

Answer 2

• Internes Sortieren: Direkter (wahlfreier) Zugriff auf jedes einzelne Folgenelement, beispielsweise im Hauptspeicher einer Rechenanlage
• Externes Sortieren: Zu sortierende Liste passt nicht komplett in den Hauptspeicher. Beispiel: Sortieren von großen Tabellen in Datenbanken
• Voraussetzung: Auf Menge der zu sortierenden Elemente muss totale (numerische) Ordnung definiert sein

Question 3

Sortieren durch direktes Einfügen (insertion sort)

Answer 3

• Die Elemente a[2], …, a[n] werden nacheinander betrachtet.
• Jedes Element a[i] wird in der bereits sortierten Teilfolge a[1], …, a[i-1] an der richtigen Stelle eingefügt.
  
  • k=aktueller Wert
  • j: von rechts nach links durchsuchen
  • Suche richtige Stelle, Verschiebe Folge mit jedem j eine Position nach rechts
  • k wird rechts von j eingefügt

Question 4

Quicksort

Answer 4

• beruht auf „Divide-and-Conquer-Technik”
• Aufruf: “quicksort(0, n-1)”, aber Vorgehen startet bei a[1]
• Zerlegung (divide):
  
  1. Wähle x (:= a[1])
  2. Suche von links: (bei a[2] beginnend) bis x < a[i]
  3. Suche von rechts bis a[j] < x
  4. Falls i<j>
     </j>
  5. Wiederhole (2), (3) und (4) so lange, bis i ≥ j
  6. Vertausche anschließend x mit a[j] und teile Folge an dieser Stelle
• Rekursion (conquer):
  
  • Wiederhole Verfahren für Teilfolgen bis diese einelementig sind
  • Aufruf nach Vertauschen (Beachte j im Code = j-1 bei Vorgehen, analog i):
    
    • if( Li < j - 1 ) { quicksort(Li, j - 1); }
    • if( j + 1 < Re ){ quicksort(j + 1, Re);

⇒ Eines der schnellsten bekannten Sortierverfahren!

Question 5

Quicksort - Varianten/Performance

Answer 5

• Varianten - Wahl des Vergleichschlüssels:
  
  • festes Element
  • zufälliges - “ -
  • Durchschnittswerte etc.
• Performance hägt ab von
  
  • Zahlenfolge
  • Wahl des Pivotelements

Question 6

Heap

Answer 6

• heap = Datenstruktur, bei der die Werte der beiden Kindknoten kleiner als der Wert ihres Vaterknotens sind (wenn die Folgenelemente als binärer Baum verstanden werden)

⇒ größtes Element an Listenanfang

• Prinzip: Vergleichen und Vertauschen von Schlüsselwerten
• Versickern: Knoten wird mit dem größten seiner Nachfolger vertauscht, falls NF vorhanden
• Blätter erfüllen immer Heapbedingung

Question 7

Heapsort - Vorgehen

Answer 7

• Erstellen des (Ausgangs-)Heaps:
  
  • Blätter erfüllen Heapbedingung automatisch
  • Versickern in Rückwärtsreihenfolge (a[n/2], …, a[1])
• Vertausche a[1] und a[n] (aufsteigend) oder spalte a[1] vorne ab (absteigend)
• Versicker Teilfolge a[2], …, a[n]

Question 8

BottomUp HeapSort

Answer 8

• in Praxis besser als Quicksort, das besser als Heapsort ist
• Wurzel wird entlang des Pfades mit größeren Kind bis zum Blattknoten abgesenkt
• neue Blattknoten muss so weit aufrücken, bis Heap-Eigenschaft wiederhergestellt ist

Question 9

Bubblesort

Answer 9

• von links nach rechts Nachbarn vergleichen & ggf. vertauschen
• wiederholen bis Folge sortiert
• letztes Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restlichen zu sortierenden Elemente kleiner bzw. größer sind
• Je nachdem, ob auf-oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser

Question 10

Shakersort

Answer 10

• abwechselnd von
  
  • links nach rechts und dann
  • von rechts nach links
  • Nachbarn vergleichen & ggf. vertauschen

⇒ Laufzeitvorteile (bestcase: O(n), worstcase: O(n²))

Question 11

Unterschiede Bubblesort und Shakersort

Answer 11

• Bubblesort durchläuft Folge immer von vorne.
• Shakersort läuft abwechselnd von links nach rechts und von rechts nach links.
• Daraus ergeben sich in einigen Fällen Laufzeitvorteile für den Shakersort.