1DigInf 05/06

Allgemeine Formulierung des Suchproblems

Suchproblem:

• In einem Behälter A befinden sich viele Elemente. Prüfe, ob ein Element e in A existiert, das eine bestimmte Eigenschaft P(e) erfüllt.

• Behälter steht dabei ganz allgemein für unterschiedliche Datenstrukturen wie:• Array• Datei• Menge• Liste• Baum• Graph• Stack• Queue

2DigInf 05/06

Allgemeine Suche in Behältern

• Entferne der Reihe nach Elemente aus dem Behälter, bis dieser leer ist oder ein Element mit der gesuchten Eigenschaft gefunden wurde.

• Programmähnlich:

• Prüfen, ob Behälter leer ist: istLeer• Ergreifen und Entfernen eines Elements aus dem

Behälter: nimmEines

3DigInf 05/06

Allgemeine Suche in Behältern

Lineare Suche in Java:

4DigInf 05/06

Allgemeine Suche in Behältern

• Mit diesem Fragment lassen sich alle Container durchsuchen, die das folgende Interface realisieren:

• Konkretisierung für Array A (auf das i-te Element wird mit A[i] zugegriffen, wahlfreier Zugriff möglich):

• Hinweis: Anzahl der Zugriffe proportional mit der Elementanzahl!

5DigInf 05/06

Binäre Suche

• Voraussetzung: • Ordnung auf dem Element-Datentyp, • sortierter Behälter

• Beispiel Array A:

• Idee: Weitersuchen in der richtigen Hälfte (a la Telefonbuch).• Verallgemeinerung: Wir suchen ein Element in einem beliebigen Teil des Arrays, der durch

Min und Max eingegrenzt wird, anfangs Min = 0, Max = N-1. Dabei gilt stets die folgende Invariante:

• Mit anderen Worten: Wenn das gesuchte Element überhaupt vorhanden ist, dann liegt es auch im noch zu untersuchenden Bereich.

6DigInf 05/06

Binäre Suche – Auf dem Weg zum Algorithmus

Funktionsweise:Wenn Max<Min breche ab, x ist nicht vorhanden, ansonsten wähle irgendeinen Index m zwischen Min und Max:Falls x = A[m] gilt, sind wir fertig, m wird returniert.Falls x < A[m], suche weiter im Bereich Min bis m-1, setze also Max auf m-1Falls x > A[m], suche weiter im Bereich m+1 bis Max, setze also Min auf m+1

Der Wert m wird dabei am Besten mittig zwischen Min und Max gewählt, also m = (Min + Max) / 2

Wenn Min ... Max aus N Elementen besteht, können wir den Bereich höchstens log2(N) mal halbieren. Um 1000 Elemente zu durchsuchen, genügen also log2(1000) = 10 Vergleiche.

7DigInf 05/06

Binäre Suche – Auf dem Weg zum Algorithmus

Illustration:

8DigInf 05/06

Binäre Suche – Formulierung als rekursive Methode

9DigInf 05/06

Lineare Suche versus binäre Suche

Binäre Suche ist deutlich effizienter, setzt allerdings auch eine geeignete Strukturierung der Daten voraus. Im Einzelnen:

• Im Behälter sind die Elemente an Positionen gespeichert.• Man kann über die Position direkt auf das einzelne Element zugreifen.• Auf dem Elementtyp ist eine Ordnung definiert.• Die Elemente sind gemäß dieser Ordnung an den Positionen platziert.

Der deutliche Effizienzunterschied kann bei häufigen Suchen rechtfertigen, dass man• alle Elemente in ein Array kopiert,• das Array sortiert,• ab dann im sortierten Array binär sucht.

10DigInf 05/06

Komplexität von Algorithmen am Beispiel des Suchens

• Unter der Komplexität eines Algorithmus versteht man grob seinen Bedarf an Ressourcen in Abhängigkeit vom Umfang der Eingabedaten. Wichtigste Ressourcen sind dabei Laufzeit und Speicherplatz.

• Laufzeit hängt im wesentlichen davon ab, wie oft die Schleifen durchlaufen werden.

• Wir unterscheiden drei Fälle:• Best case: Ein Element x mit P(x) wird beim ersten

Durchlauf gefunden.• Average case: Element wird nach der halben

Maximalzahl von Schleifendurchläufen gefunden.• Worst case: Element wird beim letzten Durchlauf

gefunden oder kommt gar nicht vor.

11DigInf 05/06

Komplexität von Algorithmen am Beispiel des Suchens

Tabelle der Laufzeitverhalten und Abschätzungen

12DigInf 05/06

Komplexitätsklassen

Sind f, g: Nat Nat Funktionen, so heißt f höchstens von der Ordnung g, falls eine Konstante C existiert, sodass für alle großen N gilt: f(N) C * g(N). Man schreibt auch f(N) = O(g(N)) und nennt diese Schreibweise O-Notation.

Diese Definition unterscheidet nicht zwischen Algorithmen, deren Aufwand nur um einen konstanten Faktor differiert. Insbesondere gilt O(log(N)) = O(log2(N)), denn log2(N) = log2(10) * log (N).

Offensichtlich gilt: O(log(N)) < O(N) < O(N2)

Wenn O(f(N)) < O(g(N)), so gilt O(f(N) + g(N)) = O(g(N)).

Insbesondere: Die polynomialen Komplexitätsklasen sind nur von der höchsten Potenz bestimmt, d.h.:O(ck * Nk + ... + c1 * N + c0) = O(Nk)

13DigInf 05/06

Komplexitätsklassen

Wertverläufe der Bearbeitungszeit (Betrachtung der Größenordnung), oberste Zeile entspricht Länge der Eingabe, Tabelleneinträge entsprechen Bearbeitungszeit

14DigInf 05/06

Komplexitätsklassen

• Pentium PC, Annahme: Zeitbedarf für eine Komplexitätseinheit = eine Mikrosekunde

• Frage: Welche Datenmengen lassen sich in vorgegebener Zeit verarbeiten?

15DigInf 05/06

Einfache Sortierverfahren

Viele Sortierverfahren empfinden alltägliche Strategien nach.

Beispiel: Aufnehmen von Spielkarten

• Insertion Sort: einzeln aufnehmen und einsortieren• Bubble Sort: alle aufnehmen, benachbarte Karten

vertauschen• Selection Sort: beim Aufnehmen offener Karten, immer

nur die niedrigste aufnehmen

16DigInf 05/06

Objekte und Schlüssel• In der Praxis werden in der Regel keine Zahlen sortiert,

sondern Objekte.

• Sortierkriterium ist dabei meist eine ausgezeichnete Menge von Objektattributen. Wenn nach diesen Attributen gesucht werden soll, spricht man von Schlüsseln.

• Beispiel: Objekte zu der Klasse

17DigInf 05/06

Objekte und Schlüssel

Für das Sortieren ist es wichtig, dass die Schlüssel von Objekten verglichen werden können, zum Beispiel für den Schlüssel „Name, Vorname“ für Studenten:

18DigInf 05/06

Rahmenbedingungen für Sortieralgorithmen

Für die Diskussion von Sortieralgorithmen nehmen wir an, dass einzelne Zeichen zu sortieren sind.

Ausgangssituation:

Sortierziel:

Weitere Annahmen und Voraussetzungen:• Zeichen sind in einem Array gespeichert• Prozedur Swap

19DigInf 05/06

Rahmenbedingungen für Sortieralgorithmen

• Die Verwendung von Swap erhöht die Lesbarkeit der folgenden Algorithmen.

• Sie garantiert die folgende Invariante:

• Das Array A ist jederzeit eine Permutation des ursprünglichen Arrays.

20DigInf 05/06

• Idee: benachbarte Felder in falscher Reihenfolge werden vertauscht.

• Mehrere Durchgänge, am Ende des ersten Durchgangs steht das größte Element ganz rechts.

• Im zweiten Durchgang kommt das zweitgrößte Element an seiner Position an.

Sortieren mit BubbleSort

21DigInf 05/06

Sortieren mit BubbleSort

22DigInf 05/06

Sortieren mit BubbleSort

23DigInf 05/06

Sortieren mit BubbleSort - Optimierung

Das Beispiel zeigt, dass schon nach 10 (statt der schlimmstenfalls nötigen 14) Durchläufen das Sortierziel erreicht ist.

Eine entsprechende Optimierung führt zu:

24DigInf 05/06

Sortieren mit BubbleSort – Laufzeit des optimierten Algorithmus

25DigInf 05/06

Sortieren mit BubbleSort – Laufzeit des optimierten Algorithmus

26DigInf 05/06

SelectionSort

• Idee: In jedem Schritt wird das kleinste (größte) der noch ungeordneten Elemente gesucht und am rechten Ende der bereits sortierten Elemente eingefügt.

• In einem Array mit dem Indexbereich [Lo...Hi] sei k die erste Position und i die Position des kleinsten Elements im noch unsortierten Bereich.

• Damit ergibt sich folgende Situation vor einem Sortierschritt

• Wenn wir nun A[k] und A[i] vertauschen, dann ist der sortierte Bereich um ein Element vergrößert:

27DigInf 05/06

SelectionSort

• Wiederholung des Tauschens bis k = Hi.

• Anwendung auf das Standardbeispiel (k=3)

28DigInf 05/06

SelectionSort

• minPos ermittelt die Position des kleinsten Elements im unsortierten Rest.

29DigInf 05/06

SelectionSort - Laufzeitbetrachtung

• äußere Schleife wird N-1 mal durchlaufen. • minPos(A,k,N) erfordert bis zu N-k Vergleiche• Also: O(N2)• Allerdings ist das C kleiner als bei BubbleSort (nur genau

ein Swap pro Durchgang)• Nachteil: Sortieren dauert immer gleich lang, egal, wie gut

das Array vorsortiert ist.