Themenbereich 5: Entwerfen von Sortieralgorithmen Flashcards
(4 cards)
Erläutern Sie die Grundzüge des Sortieralgorithmus „Bubblesort“ an einem Beispiel.
Beim Bubblesort Algorithmus wird ein Array – also eine Eingabe-Liste – immer paarweise
von links nach rechts in einer sogenannten Bubble-Phase durchlaufen. Man startet also mit der
ersten Zahl und vergleicht diese dann mit ihrem direkten Nachbarn nach dem Sortierkriterium.
Sollten beide Elemente nicht in der richtigen Reihenfolge sein, werden sie ganz einfach
miteinander vertauscht.
Danach wird direkt das nächste Paar miteinander verglichen, bis die
gesamte Liste einmal durchlaufen wurde.
Die Phase wird so oft wiederholt, bis der gesamte
Array vollständig sortiert ist.
Beispiel einer Bubble Phase Innerhalb des Beispiels wird das
folgende Array sortiert:
[5] [1] [4] [9] [0] [8] [6]
Die 5 ist größer als die 1, also tauschen wir die beiden miteinander.
Als nächstes vergleichen wir die 5 mit der 4 und tauschen auch hier die
Positionen.
Danach wird die 5 mit der 9 überprüft.
In diesem Fall wird kein Austausch benötigt.
Diesmal ist die 5 kleiner und alles bleibt wie es ist.
Weiter geht es dann mit der 9 und der 0 aber das Prinzip hast du jetzt bestimmt verstanden.
Am Ende des Durchlaufs erhalten wir diese Liste:
[5] [1] [4] [9] [0] [8] [6] [1] [5] [4] [9] [0] [8] [6] [1] [4] [5] [9] [0] [8] [6] [1] [4] [5] [9] [0] [8]
[6] [1] [4] [5] [0] [9] [8] [6] [1] [4] [5] [0] [8] [9] [6] [1] [4] [5] [0] [8] [6] [9]
Zeigen Sie das Tauschen von zwei Elementen unter Einbeziehung einer Hilfsvariablen auf.
**Speichere den Wert des ersten Elements in einer Hilfsvariablen.
**Weise dem ersten Element den Wert des zweiten Elements zu.
**Weise dem zweiten Element den Wert der Hilfsvariablen zu.
In dem Beispiel in Python werden die Werte von element1 und element2 durch Zwischenspeichern des Werts von element1 in temp, das dann den Wert von element2 annimmt, und schließlich durch Setzen von element2 auf den ursprünglichen Wert von element1 getauscht. So haben element1 und element2 ihre Werte ausgetauscht.
In welchen Bereichen der Informatik haben Sortieralgorithmen eine besondere Bedeutung?
Datenbank, Betriebssystem,Algorithmen und Datenstrukturen, Graphenalgorithmen,
Numerische Berechnungen, Kryptographie, Multimedia und Grafik.
Erläutern Sie die Grundzüge des Sortieralgorithmus „Quicksort“ an einem Beispiel (Pseudocode).
Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die
größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen.
Nach der Aufteilung sind die Elemente der linken
Liste kleiner oder gleich den Elementen der rechten Liste. Anschließend muss man also noch
jede Teilliste in sich sortieren, um die Sortierung zu vollenden.
