Suchen und Sortieren

Einer der häufigsten Aufgaben in der Informatik ist das Suchen und Sortieren von Daten. Eine großzahl der Rechner weltweit ist in der meisten Zeit nur mit dem Suchen und Sortieren von Millionen Datensätzen beschäftigt. Hierbei wird zwischen zwei verschiedenen Arten von Suchen unterschieden. Die erste Art von Suchen ist  die Suche in sortierten Datensätzen. Wenn in der Informatik etwas sortiert ist, dann spricht man von “Suchen in sortierten Folgen”.

Aber wann sind Datensätze sortiert und wann nicht ? Von einem sortierten Datensatz spricht man, wenn der Datensatz durch einen bestimmten Sortieralgorithmus nach dem Suchkriterium sortiert wurde. Auf die verschiedenen Sortieralgorithmen gehen wir in einem späteren Abschnitt noch ausführlich ein. Aber nun noch zu einer weiteren Möglichkeit der Suche in der Informatik. Bei der sequentielle Suche wird eine Folge von Elementen Schritt für Schritt durchlaufen, bis der Suchschlüssel mit dem aktuellen Element übereinstimmt. Du fragst dich nun sicher, welche der vorgestellten Suchmethode effektiver ist. Wir können dir in diesem Fall sagen, dass es darauf ankommt 😀 Um dich für die richtige Methode zu entscheiden musst du eine Aufwandsschätzung durchführen.

Aufwand

Die Aufwandsschätzung beantwortet dir folgende Fragen:

  • Wie aufwändig ist suchen?
  • Wie aufwändig ist sortieren?

=> Lohnt sich das Sortieren ?

Für die Aufwandsschätzung benötigt man Kenntnisse über die Logarithmenrechnung. Hier eine kleine Wiederholung der Logarithmenrechnung:

ab = cb = loga(c)
103 = 1000log10(1000) = 3
log (a*b) = log (a) + log (b)
log (ab) = b * log(a)

Suchkriterium != Sortierkriterium

Suchaufwand im Schnitt:

bestcase: 1

worstcase: Zugriffe = Anzahl der Datensätze

durchschnittlicher Aufwand (erforderliche Zugriffe) = Anzahl der Datensätze / 2

Der Aufwand bei dieser Suchmethode ist abhängig von der Anzahl an Datensätzen. Der Aufwand steigt linear, wenn sich die Anzahl an Datensätzen erhöht.

Suchkriterium = Sortierkriterium

Wenn das Suchkriterium dem Sortierkriterium entspricht, ist binäres Suchen möglich. Beim binären Suchen halbiert man den vorliegenden Datensatz bei jedem Zugriff. Der Aufwand ist hierbei ca:

log2 n  = durchschnittliche Anzahl an Zugriffen ( n steht hierbei für die Anzahl an Datensätzen)

weitere Aufwände

Aufwandsfunktion (n = Anzahl Daten)Beispiele
F(1)Direktzugriff
F(log2 n)Binäres Suchen
F(n)Sequentielles Suchen
F(n* log2 n)Merge- Sort
F(n2)Insertion Sort, Bubble Sort, Selection Sort
F(n3)Matrizenmultiplikation


Sortieralgorithmen

Für die Sortierung eines Datensatzes gibt es unterschiedliche Sortieralgorithmen. In der oberen Tabelle haben wir dir schon einige dieser Sortieralgorithmen aufgelistet. In diesem Teil werden wir etwas genauer auf die Funktionsweise dieser Sortieralgorithmen eingehen.

Insertion Sort

Der Insertion Sort ist das Sortieren durch Einfügen. Dieser Algorithmus ist ein einfaches Sortierverfahren, da sich der Algorithmus sehr leicht implementieren lässt und sehr effizient bei kleinen Datenmengen Arbeitet. Wenn die Datenmengen größer werden, ist es nicht mehr zu empfehlen diesen Algorithmus zu nehmen, da die Sortiergeschwindigkeit stark abnimmt (F(n2) bei n Datensätzen). Hier die Funktionsweise eines Insertion Sorts:

Selection Sort

Der Selection Sort ist ein Sortieralgorithmus nach dem Prinzip der Auswahl. Er ist wie der Insertion Sort ein einfacher Sortieralgorithmus, der sich nur in seinem Algorithmus von einem Insertion Sort unterscheiden lässt. Der Sortieraufwand ist der gleichzusetzen mit dem des Insertion Sorts. Im Folgenden werden wir dir zeigen, wie ein Selection Sort funktioniert:

Bubble Sort

Der Bubble Sort ist ein Sortieralgorithmus nach dem Prinzip des Aufsteigens. Der Algorithmus funktioniert durch ein vergleichsbasiertes Verfahren (Vergleich mit dem Nachbarn). Somit funktioniert er ähnlich wie die anderen beiden Sortieralgorithmen.

Nun werden wir dir die Funktionsweise eines Bubble Sorts demonstrieren:

Merge Sort

Der Merge Sort ist ein Suchalgorithmus, der durch das Prinzip Teile und Herrsche (“Divide and Conquer”) funktioniert. Ein Datensatz wird so oft geteilt bis alle Bestandteile isoliert vorliegen. Im nächsten Schritt werden diese dann von links nach rechts wieder zusammengefügt und nach dem gewünschten Kriterium sortiert. Hier ein Beispiel für einen Merge Sort:

Quick Sort

Der Quicksort ist ein schneller Sortieralgorithmus, der ebenfalls nach dem Teile und Herrsche Prinzip arbeitet. Er unterscheidet sich jedoch in seiner Funktionsweise vom Merge Sort. Die Datenmenge wird wie beim Merge Sort in zwei Teile unterteilt. Für die Unterteilung legt man ein Pivot Element fest. Alle Daten, die links vom Pivotelement stehen sind kleiner als das gewählte Pivotelement. Alle Daten, die rechts vom Pivotelement stehen sind größer als das Pivotelement. Um dir den Algorithmus besser zu verdeutlichen haben wir wieder ein anschauliches Beispiel für dich angefertigt: