Algorithmen

[5]

    Abbildung 5: Prinzip „Teile und Herrsche“ bei Quick Sort [6]
    static void InsertSort(IComparable[] array)
{
int i, j;
for (i = 1; i < array.Length; i++)
{
IComparable value = array[i];
j = i - 1;
while ((j >= 0) && (array[j].CompareTo(value) > 0))
{
array[j + 1] = array[j];
j=j-1;
}
array[j + 1] = value;
}
}
    Listing 2: Insert Sort in C# [7]
    procedure InsertionSort(var A: array of Integer);
var
i: Integer;
j: Integer;
tmp: Integer;
begin
for i:= 1 to high(A) do
begin
j:= i;
tmp := A[i];
while (j > 0) and (A[j-1] > tmp) do
begin
// Verschieben:
A[j]:= A[j-1];
Dec(j);
end;
A[j]:= tmp;
end;
end;
    Listing 3: Insert Sort in Delphi [8]
    Suchalgorithmen im Überblick
    Ein weiteres wichtiges Teilgebiet der Algorithmenentwicklung sind Suchverfahren. Dabei sollen bestimmte Informationen aus einer großen Datenmenge gefiltert werden. Die Suche kann sowohl in unsortierten als auch in sortierten Daten erfolgen. Im Regelfall ist jedoch ein vorheriges Sortieren der Daten angebracht. Einen Überblick über einige Suchverfahren gibt Tabelle 3.
Name des Verfahrens
Beschreibung
Lineare Suche
Die lineare Suche wird auch als sequenzielle Suche bezeichnet und stellt die einfachste Form dar. Dabei wird jedes Element mit dem Suchkriterium verglichen, d. h. mittels einer Schleife werden alle Elemente untersucht. Die Vorteile sind:
einfachste Implementierung
auf allen Datenspeichern und Strukturen (Listen, Arrays ...) anwendbar
ein vorheriges Sortieren der Daten ist nicht notwendig
    Der entscheidende Nachteil der linearen Suche ist, dass alle Datensätze zu betrachten sind und damit der Suchvorgang lange dauern kann. Das ist besonders dann der Fall, wenn sich das gesuchte Element am Ende der Liste befindet. Die lineare Suche kann dann angewendet werden, wenn nur relativ wenige Datensätze zu durchsuchen sind. Ebenfalls kommt diese Form der Suche zur Anwendung, wenn keine Sortierung/Indizierung bezüglich des Suchfelds vorliegt.
Binäre Suche
Auch hier gilt das Prinzip „Teile und herrsche“. Voraussetzung ist, dass die Daten sortiert vorliegen. Das ist im Vorfeld ggf. über einen Sortieralgorithmus sicherzustellen. Die Liste der Daten wird in zwei Teile gespalten. Ist das aktuelle Element größer oder kleiner als das gesuchte Element wird links oder rechts der Suchvorgang fortgesetzt. Es entspricht dem Suchen eines Buchs in einer Bibliothek, wenn die Bücher alphabetisch geordnet in den Regalen stehen.
Suchbäume
Von besonderem Interesse ist der so genannte Binärbaum, d. h. ein Baum der Ordnung zwei. Jeder Knoten besitzt höchstens zwei Kinder. Ziel des Einsatzes eines binären Suchbaums ist es also, die Suchvorgänge zu verkürzen. Besonders wichtig ist das bei umfangreichen Datenbeständen. Da die Elemente in einem Baum nicht linear nebeneinander angeordnet sind, existieren verschiedene Varianten, die Informationen in einem Baum zu suchen bzw. die Knoten eines Baums zu durchlaufen. Das Durchlaufen eines Baums wird auch als Traversierung bezeichnet. Folgende Durchlaufordnungen von Binärbäumen sind üblich:
Preorder-Reihenfolge: Es wird zuerst die Wurzel des Baums besucht. Danach werden rekursiv der linke und dann der rechte Teilbaum durchlaufen
Postorder-Reihenfolge: Zuerst werden die Kind-Knoten (rekursiv) durchlaufen, danach der Eltern-Knoten besucht.
Inorder-Reihenfolge: Der Eltern-Knoten wird zwischen den beiden Kind-Knoten besucht.
    Für die Verwendung als binärer Suchbaum muss ein Erkennungsmerkmal – ein Schlüssel ( key ) – eingefügt werden. Anhand des Schlüssels werden die Daten innerhalb des Baums abgelegt. Dabei sollte der Schlüssel selbst Bestandteil der Daten, oder basierend auf (Teil-) Daten zu errechnen sein. (Pseudocode: Listing 4)
    Tabelle 3: Einige Suchverfahren im Überblick
    algorithm search(v, k)
if v <> null then
if k < key(v) then
search(left(v), k)
else
if k > key(v) then
search(right(v), k)
else
Beende Suche
end if
end if
else
Beende Suche
end if
end algorithm
    Listing 4

2 Spezielle Optimierungsverfahren von der Natur lernen
    Sie suchen den kürzesten Weg zwischen zwei Orten? Dann machen Sie es doch wie die Ameisen! Der nachfolgende Abschnitt widmet sich einem Thema aus der theoretischen Informatik. Es geht um die Ermittlung von Lösungen für mathematische Optimierungsprobleme, für die exakte Rechenverfahren nicht existieren oder zu aufwändig sind. Zum Einsatz kommen so genannte Metaheuristiken. Um was es dabei geht, können Sie hier erfahren.
    Der zweite Teil des shortcuts widmet sich