SORTIEREN UND SUCHEN
 (Zusammenstellung FH München, Informatik/Mathematik  Prof. Dr. R. Schiedermeier - Vorlesung "Programmieren I")

   Suchalgorithmen

Lineare Suche
Binäre Suche
Zeitkomplexität

Einfache Sortieralgorithmen

Bubblesort
Selection Sort
Insertion Sort
Shell-Sort
Vergleich der Sortieralgorithmen

Suchalgorithmen

Im Zusammenhang mit Vektoren bzw Arrays stellt sich schnell das Problem, ein Element mit bestimmten Eigenschaften zu suchen bzw. sein Vorkommen oder Fehlen im Vektor zu festzustellen. Zur diesem Zweck werden Suchalgorithmen benutzt. Es gibt viele unterschiedliche Suchalgorithmen, die jeweils auf spezifischen Voraussetzungen beruhen und bestimmte Eigenschaften haben.
Im folgenden werden zwei Suchalgorithmen vorgestellt, die lineare Suche und die binäre Suche.

Lineare Suche

Die lineare Suche ist ein sehr einfacher Algorithmus, der auf jede Sequenz von Elementen, wie z.B. ein Vektor, anwendbar ist. Das folgende Struktogramm zeigt, wie mit der linearen Suche das kleinste Element in einem Vektor gefunden werden kann:

Dieser sehr allgemeine Fall der linearen Suche nach einem unbekannten Element ist verhältnismäßig langsam, weil alle Elemente überprüft werden.

Ein ähnliches Problem ist die Suche nach einem bekannten Element, wie z.B. nach einer bestimmten Spielkarte in einem Kartenstapel. 
In diesem Fall kann die Suche abgebrochen werden, sobald das betreffende Element gefunden worden ist.

Bei dieser Art der Suche muß im Durchschnitt noch die Hälfte aller Elemente überprüft werden.

Die Idee hinter der binären Suche ist einfach: Zuerst wird das mittlere Vektor-Element überprüft. Wenn es kleiner als das gesuchte Element ist, muß das gesuchte Element in der hinteren Hälfte stecken, wenn es überhaupt vorkommt. Andernfalls muß nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muß nicht mehr betrachtet werden.

Mit jeder Hälfte verfährt man nun genauso: Das mittlere Element liefert die Entscheidung darüber, wo weitergesucht werden muß.

Der Algorithmus kennt zu jedem Zeitpunkt einen Suchbereich, dessen Länge sich von Schritt zu Schritt halbiert. Wenn der Suchbereich auf 1 Element geschrumpft ist, ist die Suche beendet: Das eine Element ist das gesuchte Element, oder das gesuchte Element kommt nicht vor.

Das folgende Struktogramm zeigt den Algorithmus der binären Suche:

Als Maß für die Geschwindigkeit von Algorithmen nennt man ihre Zeitkomplexität. Dabei geht es nicht um exakte Aussagen, sondern nur um Größenordnungen. Man gibt an, wie sich die Laufzeit eines Algorithmus ändert, wenn sich das Datenvolumen ändert.

Die lineare Suche hat eine Zeitkomplexität von O(n). Das bedeutet, daß die Laufzeit proportional zur Zahl der Vektor-Element steigt. Die binäre Suche hat eine Zeitkomplexität von O(log₂(n)). Das bedeutet, daß die Laufzeit nur im Verhältnis zum Zweierlogarithmus der Anzahl der Vektor-Element steigt.

Ebenso wie der Zeitbedarf läßt sich der Platzbedarf eines Algorithmus messen. Dieses Maß nennt man die Speicherplatzkomplexität eines Algorithmus. An dieser Stelle spielt die Speicherplatzkomplexität noch keine Rolle.

Sortieralgorithmen setzen voraus, daß je zwei Elemente nach irgendeinem Kriterium vergleichbar sind. Der Vergleich kann so einfach sein wie die Größe von Zahlen oder so kompliziert, wie die Bewertung der Siegchancen einer Stellung im Schachspiel. Für die Sortieralgorithmen spielt die Art der verglichenen Information keine Rolle.

Die Qualität von Sortieralgorithmen läßt sich unter verschiedenen Gesichtspunkten vergleichen. Dabei ist in erster Linie die Geschwindigkeit interessant, die üblicherweise an der Anzahl Elementvergleiche und der Anzahl Kopieraktionen gemessen wird. Die konkrete Anzahl Operationen hängt stark vom Datensatz ab. Deshalb berücksichtigt man den besten, den schlechtesten und den durchschnittlichen Fall. Unter Umständen ist auch das Verhalten für einen teilweise vorsortierten Datensatz von Interesse.

Es gibt noch viele weitere Sortieralgorithmen. Allen hier beschriebenen Algorithmen ist gemeinsam, daß sie eine konstante Menge an zusätzlichem Speicherplatz brauchen, unabhängig vom Umfang des Datensatzes. Man nennt die Algorithmen deshalb einfache Sortieralgorithmen. Der schnelle "Quicksort"-Algorithmus ist dagegen kein einfacher Sortieralgorithmus. Quicksort wird an anderer Stelle eingeführt. 
Alle unten beschriebenen Algorithmen sind korrekt in dem Sinn, daß sie das geforderte Ziel erreichen. Trotzdem arbeiten die Algorithmen nach sehr unterschiedlichen Methoden.
Für die weitere Diskussion wird angenommen, daß der Datensatz aufsteigend sortiert werden soll. Mit anderen Worten: Nach dem Sortieren steht das kleinste Element am Anfang und das größte am Ende.

Der Name "Bubblesort" rührt von der bildhaften Vorstellung her, daß der Algorithmus leichte Elemente (= kleine Werte) wie Blasen in einer Flüssigkeit nach oben (= vorne im Datensatz) steigen läßt.
Bubblesort beruht auf der folgenden Idee: Der Datensatz wird vom Anfang zum Ende durchkämmt und die Elemente dabei paarweise verglichen. Wenn beide in der richtigen Reihenfolge stehen (das kleinere zuerst, das größere hinterher), dann wird mit dem nächsten Paar fortgefahren. Wenn beide in der falschen Reihenfolge stehen, werden sie zuerst vertauscht. Das größte Element wandert dabei an das Ende des Datensatzes.

Dann wird der Prozeß wiederholt, aber ohne das letzte Element. Im nächsten Durchgang werden die letzten beiden Elemente ausgelassen usw. Der Datensatz ist vollständig sortiert, wenn nur noch ein Element zu "sortieren" ist.

Das folgende Struktogramm zeigt den Algorithmus schematisch:

(Für dieses und alle weiteren Struktogramme wird angenommen, daß der Datensatz (max + 1) Elemente umfaßt und in einem Vektor a mit Indizes 0 bis max gespeichert ist.)

Das folgende Beispiel (8 Elemente, d.h. max = 7) zeigt die Arbeitsweise. Ein - zwischen zwei Elementen bedeutet, daß ihre Reihenfolge paßt. Ein × zwischen zwei Elementen bedeutet, daß sie in der falschen Reihenfolge stehen und von Bubblesort vertauscht werden. Der senkrechte Strich markiert den Bereich, in dem gearbeitet wird.

n = 7
44 - 55   12   42   94   18   06   67
44   55 × 12   42   94   18   06   67
44   12   55 × 42   94   18   06   67
44   12   42   55 - 94   18   06   67
44   12   42   55   94 × 18   06   67
44   12   42   55   18   94 × 06   67
44   12   42   55   18   06   94 × 67
n = 6
44 × 12   42   55   18   06   67 | 94
12   44 × 42   55   18   06   67 | 94
12   42   44 - 55   18   06   67 | 94
12   42   44   55 × 18   06   67 | 94
12   42   44   18   55 × 06   67 | 94
12   42   44   18   06   55 - 67 | 94
n = 5
12 - 42   44   18   06   55 | 67   94
12   42 - 44   18   06   55 | 67   94
12   42   44 × 18   06   55 | 67   94
12   42   18   44 × 06   55 | 67   94
12   42   18   06   44 - 55 | 67   94
n = 4
12 - 42   18   06   44 | 55   67   94
12   42 × 18   06   44 | 55   67   94
12   18   42 × 06   44 | 55   67   94
12   18   06   42 - 44 | 55   67   94
n = 3
12 - 18   06   42 | 44   55   67   94
12   18 × 06   42 | 44   55   67   94
12   06   18 - 42 | 44   55   67   94
n = 2
12 × 06   18 | 42   44   55   67   94
06   12 - 18 | 42   44   55   67   94
n = 1
06 - 12 | 18   42   44   55   67   94

Bubblesort folgt einem so einleuchtenden Mechanismus, daß der Algorithmus oft aus Zeitmangel (oder Ungeduld) gewählt wird, obwohl bessere Algorithmen verfügbar sind. (Für kleine oder weitgehend sortierte Datensätze ist Bubblesort sogar oft eine gute Wahl.)

Für einen durchschnittlichen Datensatz braucht Bubblesort in der Größenordnung von O(½n²) Vergleiche und halb so viele Vertauschungen.

Selection Sort arbeitet nach folgendem Mechanismus: Der Datensatz nach dem kleinsten Element durchsucht, dann wird dieses an den Anfang gesetzt. Im nächsten Schritt wird das erste Element ausgelassen und der gleiche Prozeß mit dem Rest des Datensatzes wiederholt. Der Algorithmus kommt zum Ende, wenn nur noch 1 Element übrig ist.

Der Vorteil von Selection Sort gegenüber Bubblesort liegt in der Art, wie ein Element an seinen Zielort transportiert wird: Bei Bubblesort wird ein Element an seinem Quellort herausgenommen, alle Elemente zwischen dem Quellort und dem Zielort um eine Position verschoben und dann das Elemente an seinem Zielort eingefügt. Selection Sort vertauscht nur die beiden Elemente am Quell- und Zielort und läßt alle Elemente dazwischen stehen.

Das folgende Struktogramm zeigt den Algorithmus schematisch:

Das folgende Beispiel zeigt die Arbeitsweise. Die jeweils farbig gedruckten Elemente wurden vertauscht. Der senkrechte Strich markiert den Anfang des bearbeiteten Bereichs.

n = 0
44   55   12   42   94   18   06   67
min = 6
06   55   12   42   94   18   44   67

   | n = 1
06 | 55   12   42   94   18   44   67
   | min = 2
06 | 12   55   42   94   18   44   67

        | n = 2
06   12 | 18   42   94   55   44   67
        | min = 2
keine Änderung

             | n = 3
06   12   18 | 42   94   55   44   67
             | min = 3
keine Änderung

                  | n = 4
06   12   18   42 | 94   55   44   67
                  | min = 6
06   12   18   42 | 44   55   94   67

                       | n = 5
06   12   18   42   44 | 55   94   67
                       | min = 5
keine Änderung

                            | n = 6
06   12   18   42   44   55 | 94   67
                            | min = 7
06   12   18   42   44   55 | 67   94

n = 7
keine Änderung

Für einen durchschnittlichen Datensatz braucht Selection Sort etwa O(½n²) Vergleiche und O(n) Vertauschungen. Selection Sort ist gegenüber Bubblesort im Vorteil, wenn das Vertauschen (d.h. Kopieren) von Elementen aufwendig ist.

Das folgende Struktogramm zeigt den Algorithmus schematisch:

Das folgende Beispiel zeigt die Arbeitsweise. Das jeweils farbig gedruckte Element ist das ausgewählte Element. Das Kreuz markiert die gefundene Einfügestelle.

n = 1
 44  ×55   12   42   94   18   06   67
 44   55   12   42   94   18   06   67
n = 2
×44   55   12   42   94   18   06   67
 12   44   55   42   94   18   06   67
n = 3
 12  ×44   55   42   94   18   06   67
 12   42   44   55   94   18   06   67
n = 4
 12   42   44   55  ×94   18   06   67
 12   42   44   55   94   18   06   67
n = 5
 12  ×42   44   55   94   18   06   67
 12   18   42   44   55   94   06   67
n = 6
×12   18   42   44   55   94   06   67
 06   12   18   42   44   55   94   67
n = 7
 06   12   18   42   44   55  ×94   67
 06   12   18   42   44   55   67   94

Für einen durchschnittlichen Datensatz braucht Insertion Sort etwa O(n²/4) Vergleiche und O(n²/8) Vertauschungen. Gegenüber Selection Sort vergleicht Insertion Sort weniger, kopiert aber mehr. (Diese Aussage gilt nur für einen hinreichend großen Datensatz.)

In einem ersten Durchgang wird der Datensatz in vier Teilfolgen von Elementen getrennt. Die erste Teilfolge enthält das 1., 5., 9., 13. usw. Element. Die zweite Teilfolge das 2., 6., 10., 14. usw. Element. Die dritte und vierte Teilfolge sind entsprechend verzahnt. Das folgende Bild zeigt die Teilfolgen der Schrittweite 4:

Jede Teilfolge wird nun für sich und getrennt von den anderen Teilfolgen sortiert. Dazu wird irgendein anderer Sortieralgorithmus benutzt, im unten abgebildeten Struktogramm z.B. Insertion Sort. Im nächsten Durchgang werden weniger Teilfolgen gebildet, z.B. nur noch 2. Beide Teilfolgen werden wieder getrennt sortiert. Am Ende wird der ganze Datensatz als eine einzige Teilfolge sortiert.

Die fallende Abfolge der Schrittweiten von 4-2-1 ist willkürlich gewählt und keineswegs optimal. Durch Experimente hat sich sogar herausgestellt, daß Zweierpotenzen eine schlechte Wahl sind. Mit teilerfremden Schrittweiten ergeben sich viel bessere Resultate. Eine gute Wahl sind Schrittweiten, die sich nach der Formel 3*n+1 für n = 1, 2, 3, ... ergeben, also 1-4-13-40- usw.

Das folgende Struktogramm zeigt den Algorithmus schematisch:

Auf eine Skizze der Arbeitsweise wird verzichtet, weil sich das Verhalten von Shell-Sort an einem kleinen Beispiel nicht sehr anschaulich zeigen läßt.

Die Qualität von Shell-Sort läßt sich sehr schwer theoretisch errechnen. Experimentelle Messungen weisen auf etwa O(n^1.25) Vergleiche und ebenso viele Vertauschungen hin. Shell-Sort ist damit unter den einfachen Sortieralgorithmen der Schnellste.