Such- und Sortieralgorithmen

Page 1

lineare Suche

Bei der linearen Suche wird die Datenmenge von vorne nach hinten auf ein bestimmtes Element überprüft bis dieses gefunden ist, bzw. bis festgestellt werden kann, dass sich das Objekt nicht in der Datenmenge befindet.

Page 2

Binäre Suche (Divide-And-Conquer-Algorithmus)

Voraussetzung für dieses Verfahren ist, das die Datenmenge bereits vorsortiert ist (hier aufsteigend)

Ggesucht ist das Element "a".

Bei der binären Suche wird sich das mittlere Element angeschaut. Es gibt drei Fälle:

das mittlere Element ist "a" (d[m] == a) --> gefunden

das mittlere Element ist kleiner als "a" (d[m] < a): --> wende binäre suche auf der rechten Seite an

das mittlere Element ist größer als "a" (d[m] > a): --> wende binäre suche auf der linken Seite

Page 3

Selectionsort

Unterscheidung zwischen MinSort: Sortierung von klein nach groß und MaxSort: Sortierung von groß nach klein

Beim Selectionsort-Verfahren wird die Datenstruktur auf das kleinste (MinSort) bzw. das größte Element (MaxSort) untersucht.

Hierbei wird die Datenmenge durchgegangen und z.b. das erste unsortierte Element als Vergleichs Element für alle anderen Elemente gewählt.

Es kommt in einem Zwischenspeicher. Wird ein kleineres Element gefunden kommt dieses stattdessen in den Zwischenspeicher.

Nach dem Durchlaufen der Datenstruktur wird das Element im Zwischenspeicher an die erste Stelle gesetzt.

Page 4

Insertionsort

bBeim Insertionsort-Verfahren (Sortieren durch Einfügen) werden die Zahlen/Daten immer anhand eines zufällig ausgewählten ersten Elements (Pivotelement) geordnet. Je nachdem, ob sie größer oder kleiner sind, werden sie rechts oder links in die neue Folge einsortiert.

Page 5

Bubblesort

Beim Bubblesort-Verfahren wird eine Reihe von Zahlen auf- oder absteigend geordnet. Dabei werden immer zwei Elemente die in einer Datenstruktur nebeneinander liegen verglichen und geordnet. Bei einer aufsteigenden Ordnungsfolge wird die größere Zahl nach rechts geordnet. Nach dem Ende des ersten Durchlaufs liegt die größte Zahl rechts.

Page 6

Quicksort

Zunächst wird die zu sortierende Liste in zwei Listen (linke und rechte Teilliste) getrennt. Dabei wählt Quicksort ein Pivotelement aus der Liste aus.

Aalle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste und alle die größer sind in die rechte Teilliste.

Nun wendet sich Quicksort rekursiv auf die rechte und auf die linke Seite an.