Sortierte Folgen WS13-14

Aus ProgrammingWiki

Archivierte Version vom 2013-12-15T13:53:26+00:00. Aktuelle Version

Autoren: Dominik Bitterlich; Alexander Häse

Einleitung

Sortierte Folgen

In der Informatik ist eine Folge eine Aneinanderreihung von Symbolen eines Alphabets. Ein Alphabet ist eine endliche Menge von voneinander unterscheidbaren Symbolen, die aus Zeichen oder Buchstaben bestehen. Diese können mit Hilfe bestimmter Algorithmen sortiert werden. Bekannte Sortieralgorithmen sind Selection Sort, Insertion Sort, Quicksort, Countingsort und Heapsort. Die neu entstandene Folge nennt man Sortierte Folge. Diese Folgen können in der Informatik zum Beispiel in Arrays oder Listen umgesetzt werden.

Insbesondere bei einer sortierten Liste sind die Knoten nicht in der sequentiellen Reihenfolge ihrer Eingabe angeordnet, sondern werden nach bestimmten Sortierkriterien (z.B. aufsteigend oder absteigend) geordnet. Sortierte Listen haben Vorteile gegenüber unsortierten Listen – Daten können schneller aufgefunden werden – dies gilt insbesondere für beidseitig verkettete Listen. Denn es kann schon vor Beginn des Suchvorgangs ermittelt werden, ob das gesuchte Element eher am Ende oder am Anfang der Liste zu finden sein wird. Entsprechend kann der Suchvorgang am Ende oder am Anfang der Liste begonnen werden, was die Suchzeit erheblich verkürzt.

Suchen in einer sortierten Folge

Algorithmisches Problem

Bei der Suche in einer sortieren Folge ist es das Ziel ein bestimmtes Element k in einer Menge M zu finden und z.B. dessen Index auszugeben. Eingegeben werden soll eine endliche, aufsteigend sortierte Folge e_0, e_1… e_n von Elementen aus einer Menge M, auf der eine Ordnung “<” gegeben ist. Außerdem soll ein Element k ∈ M, welches gesucht werden soll angeben werden. Ausgeben werden soll der Index des Elementes, i ∈ {0, 1 … n} sodass e_i = k gilt, vorausgesetzt ein solcher Index existiert. Ansonsten wird „nicht enthalten“ ausgegeben werden.

Beispiele

Beispiel 1:

M sei die Menge der ganzen Zahlen und die gegebene Ordnung “<” auf M ist die übliche größer/kleiner Beziehung zwischen zwei ganzen Zahlen.

Die gegebene, aufsteigend sortierte Folge sei:

4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211

Gesucht werden soll nach k = 35.

Die gewünschte Ausgabe ist der Index 8.

Die gegebene, aufsteigend sortierte Folge sei:

4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211

Gesucht werden soll nach k = 17.

Die gewünschte Ausgabe ist nicht enthalten.

Beispiel 2:

M sei die Menge der Wörter der deutschen Sprache und die gegebene Ordnung “<” auf M ist die Reihenfolge, in der die Wörter im Duden erscheinen oder auch lexikographische Ordnung genannt.

Die gegebene, aufsteigend sortierte Folge sei:

alt, beige, braun, eng, gesund, japanisch, jung, xenophob

Gesucht werden soll nach k = kalt.

Die gewünschte Ausgabe ist nicht enthalten.

Lineare Suche

Lineare Suche ist ein Algorithmus, der auch unter dem Namen sequentielle Suche bekannt ist. Er ist der einfachste Suchalgorithmus überhaupt. Die Aufgabe besteht hier darin, ein Element in einer Liste oder einem Array mit n Elementen zu finden.

Die Arbeitsweise ist hier folgende:

1. Gehe die Indizes i der Elemente in der gegebenen sortierten Folge beginnend bei 0 einen nach dem anderen durch.

1.1 Falls e_i gleich k ist, dann brich die Suche ab und gib den Index i aus.

1.2 Sonst

1.2.1 Falls k < e_i ist, dann brich die Suche ab und gib nicht enthalten aus.

1.2.2 Sonst gehe zum nächsten Element in der Folge.

2. Falls die Suche nicht zwischendurch abgebrochen wurde, gib nicht enthalten aus.

Umsetzen kann man den Algorithmus nun mittels Array oder mittles verketteten List.

Umsetzung in Java mittels Array

static int LineareSucheArray (int[] listOfNumbers, int k)
{
  for(int i=0; i<listOfNumbers.length; i =i+1)
  {
   if (listOfNumbers [i]==k)
   {
    return i;
   }
    else
   {
     if (k < listOfNumbers [i])
     {
      return -1;
     }
    }  
   } 
   return -1;
}

int[] Folge = {4,6,8,9,13,15,16,21,35,47,51,126,211};
int k = 35;
int result = LineareSucheArray(Folge, k);
if (result < 0)
{
 System.out.println("Nicht enthalten"); 
}
else
{
System.out.println ("Gefundener Index:  "+result);
}

Umsetzung in Java mittels verketteter Liste

public class SeqSucheListe
{
   static int sequentielleSucheVerketteteListe(MyLinkedList l, int k)
   {
      //Zum Merken des aktuellen Listenelements
      MyListElement e = l.head;

      for(int i = 0; i < l.numberOfElements; i++)
      {
         if(e.z == k) 
         {
            //passenden Index gefunden
            return i;
         }
         else
         {
            if(k < e.z) 
            {
               //k nicht in Folge enthalten
               return -1;
            }
            else
            {
               //Gehe zum naechsten Listenelement
               e = e.next;
            }
         }
      }
      //k nicht in Folge enthalten
      return -1;
   }

Analyse der linearen Suche

Die Analyse dieses Algorithmus im Rahmen dieser Vorlesung wird aus zwei Schritten bestehen:

1. Es muss gezeigt werden, dass dieser Algorithmus für alle zulässigen Eingaben das Gewünschte leistet
2. Es muss abgeschätzt werden, wie lange der Algorithmus im schlimmsten Fall - worst case braucht.

Dass die sequentielle Suche das Gewünschte leistet, scheint erst einmal klar zu sein. Also wird sich eingehender mit der Laufzeit des Algorithmus beschäftigt.

Annahmen zur Analyse der Laufzeit

Es wird angenommen, dass die Ausführung etwa folgender Bausteine eines Algorithmus auf jedem Rechner nach einer bestimmten Zeit abgeschlossen ist, die nicht von der Eingabe abhängen:

Vergleich
Zuweisung eines Wertes an eine Variable
Addition von zwei ganzen Zahlen
Rückgabe eines Wertes aus einer Methode

Außerdem der wird festgehalten das diese Anweisungen/Befehle in konstanter Zeit ausgeführt werden können und sie werden als elementare Anweisungen/Befehle bezeichnet.

Laufzeit in Abhängigkeit von der Eingabe

Sich Gedanken über die Laufzeit eines Algorithmus zu machen, bedeutet also zu zählen, wie viele elementare Anweisungen insgesamt im Algorithmus ausgeführt werden. Diese Anzahl wird aber in den meisten Fällen davon abhängen, welche Eingabe dem Algorithmus übergeben wurde.

Beispiele: Der Einfachheit halber zählen wir erst einmal nur die Vergleiche, die zwischen k und Elementen aus M in der gegebenen Folge durchgeführt werden.

Folge: 4, 6, 8, 9, 13, 15, 16, 21, 35, 47, 51, 126, 211
k = 8
Die Anzahl der Vergleiche beträgt 5: zwei Mal mit 4, zwei Mal mit 6, ein Mal mit 8

Folge: 4, 6, 8, 9, 13, 15, 16, 21, 35, 47, 51, 126, 211
k = 7
Die Anzahl der Vergleiche beträgt 6: zwei Mal mit 4, zwei Mal mit 6, zwei Mal mit 8

Folge: 4, 6, 8, 9, 13, 15, 16, 21, 35, 47, 51, 126, 211
k = 300
Die Anzahl der Vergleiche beträgt 26: jeweils zwei Mal mit jedem Element der Folge

Laufzeit im schlimmsten Fall (worst case)

In dieser Vorlesung wird sich für die größte Laufzeit interessiert , die man für alle zulässigen Eingaben erhalten kann (worst case Analyse). Bei der linearen Suche gilt offenbar: Die Suche nach einem Element k in einer sortieren Folge mit n Elementen benötigt nie mehr als 2n Vergleiche ( von k mit Elementen aus der gegebenen Folge). Es kann also die Anzahl V dieser Vergleiche im worst case als Funktion darstellen:

V: \mathbb{N}\rightarrow \mathbb{N} mit V(n)= 2n

Analog kann dieser Algorithmus als eine Funktion:

T: \mathbb{N}\rightarrow \mathbb{N}

wobei T(n) dann die maximale Anzahl von elementaren Anweisungen ist (nicht nur Vergleiche!), die für eine Eingabefolge mit n Elementen ausgeführt werden.

Laufzeit im worst case auf einem Array

static int LineareSucheArray (int[] listOfNumbers, int k)
{
   for(int i=0; i<listOfNumbers.length; i =i+1)
   {
      if (listOfNumbers [i]==k)
      {
         //passenden Index gefunden
         return i;
      }
      else
      {
         if (k < listOfNumbers [i])
         {
            //k nicht in Folge enthalten
            return -1;
         }
      }  
   } 
   //k nicht in Folge enthalten    
   return -1;
}

Man erhält: T(n) = 5n + 3

Laufzeit im worst case auf einer verketteten List

static int LineareSucheVerketteteListe(VerketteteListe Folge, int k)
   {
      //Zum Merken des aktuellen Listenelements
      ListenElement e = Folge.head;

      for(int i = 0; i < Folge.anzahlElemente; i+1)
      {
         if(e.z == k) 
         {
            //passenden Index gefunden
            return i;
         }
         else
         {
            if(k < e.z) 
            {
               //k nicht in Folge enthalten
               return -1;
            }
            else
            {
               //Gehe zum naechsten Listenelement
               e = e.next;
            }
         }
      }
      //k nicht in Folge enthalten
      return -1;
   }

Man erhält: T(n)=6n+4

Vergleich Laufzeit Lineare Suche in einem Array und in einer verketteten List

n	lineare Suche Array: T(n)=5n+3	lineare Suche Linked List: T(n)=6n+4
4	23	28
16	83	100
256	1283	1540
4096	20483	24500
65536	327683	393220
1048576	5242883	6291460
16777216	83886083	100663300

Idee zur Beschleunigung der Suche

Wenn die sortierte Folge als Array gegeben ist, dann kann k im ersten Schritt mit einem beliebigen Element in der sortierten Folge verglichen werden. Man muss also nicht von vorn nach hinten durchlaufen wie in einer verketteten Liste. Beispiel: k = 37 und die sortierte Folge sei wieder:

4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211

Man kann k mit dem Element an Position 3 vergleichen(also mit der 9).

Ergebnis: Wenn die 37 überhaupt in der sortierten Folge enthalten ist, dann muss sie an einer Position größer oder gleich 4 stehen.

Beispiel: k = 37 und die sortierte Folge sei wieder:

4; 6; 8; 9; 13; 15; 16; 21; 35; 47; 51; 126; 211

Ebenso könnten wir k mit dem Element an Position 9 vergleichen (also mit der 47).

Ergebnis: Wenn die 37 überhaupt in der sortierten Folge enthalten ist, dann muss sie an einer Position kleiner oder gleich 8 stehen.

Beachte: In beiden Fällen führt ein Vergleich zum Ausschluss einer ganzen Reihe von Elementen der sortierten Folge für die weitere Suche.

Man möchte nun gern eine Garantie folgender Art: Nach dem Vergleich von k mit einem geeigneten Element der sortierten Folge können immer mindestens soundso viele Elemente von der weiteren Suche ausgeschlossen werden.

Mit dem Element an welcher Position sollte man k also zuerst vergleichen?

Algorithmus binäre Suche

Gegeben ist eine sortierte Folge in einem Array A der Länge n und das gesuchte Element k.

1.Mit u und o seien im Folgenden immer die erste und die letzte Position im Array bezeichnet, zwischen denen k liegen muss (wenn es überhaupt in A enthalten ist).

2.Setze u = 0 und o = n -1.

3. Solange u <=o

3.1 Berechne p=[(o+u)/2].

3.2 Falls A[p] gleich k ist, brich die Suche ab und gib die Position p aus.

3.3 Sonst

3.3.1 Falls A[p] kleiner als k ist, setze u =p+1.

3.3.2 Sonst setze o = p -1

4. Gib Nicht enthalten aus

Umsetzung in Java

static int binaereSucheArray(int[] listOfNumbers, int k) {
	int u = 0;
	int o = listOfNumbers.length - 1;
	int p;	
	while (u<=o) {
		p=(u+o)/2;
		if (listOfNumbers[p] == k) {
			return p;
		} else {
			if (listOfNumbers[p] <k) {
				u = p + 1;
			} else {
				o = p - 1;
			}
		}
	}
        return -1;
}

int[] folge = {4,6,8,9,13,15,16,21,35,47,51,126,211};
	int k = 35;	
	int result = binaereSucheArray(folge, k);	
	if(result < 0) {
		System.out.println("Nicht enthalten!");
	} else {
		System.out.println("Gefundener Index: " + result);
	}

Laufzeit der binären Suche im worst case

Wie viele Durchläufe im worst case?

Vergleich Laufzeit Lineare Suche und binäre Suche

n	lineare Suche: T(n)=5n+3	binäre Suche: T(n)<=8log_2 n +13
4	23	29
16	83	45
256	1283	77
4096	20483	109
65536	327683	141
1048576	5242883	163
16777216	83886083	205

In den meisten Fällen ist man bei der Analyse der Laufzeit nur am asymptotischen Verhalten der Funktion T(n) interessiert welche in der O-Notation festgehalten ist:

Die worst case Laufzeit der sequentiellen Suche in einer sortierten Folge von n Elementen ist in O(n).
Die worst case Laufzeit der binären Suche in einer sortierten Folge von n Elementen ist in O(log_2 n).

Bei dieser Analyse sollte jedoch zusätzlich erwähnt werden, dass diese Laufzeit abhängig von der Laufzeit des eventuell voran gegangenen Sortieralgorithmus ist.

Name	Best Case	Average Case	Worst Case
Selection Sort	\mathcal{O}(n^2)	\mathcal{O}(n^2)	\mathcal{O}(n^2)
Insertion Sort	\mathcal{O}(n)	\mathcal{O}(n^2)	\mathcal{O}(n^2)
Mergesort	\mathcal{O}(n \cdot log(n))	\mathcal{O}(n \cdot log(n))	\mathcal{O}(n \cdot log(n))
Quicksort	\mathcal{O}(n \cdot log(n))	\mathcal{O}(n \cdot log(n))	\mathcal{O}(n^2)
Countingsort	\mathcal{O}(n+m)	\mathcal{O}(n+m)	\mathcal{O}(n+m)
Heapsort	\mathcal{O}(n \cdot log(n))	\mathcal{O}(n \cdot log(n))	\mathcal{O}(n \cdot log(n))

Einfügevorgang in einer sortierten Liste

Der interne Aufbau einer sortierten Liste unterscheidet sich nur unwesentlich von einer unsortierten Liste. Wichtig ist, dass sie nicht nachträglich sortiert (wie z.B. bei Arrays üblich), sondern von Anfang an sortiert aufgebaut wird. Das heisst: Bereits beim Einfügen eines neuen Elements erhält dieses seine richtige Position in der Sortierreihenfolge - ein neuer Knoten wird nicht einfach an das Listenende angehängt, sondern an der passenden Position in die Liste eingefügt.

Die Liste wird elementweise durchlaufen und dabei durch eine Vergleichs-operation mit den bereits vorhandenen Elementdaten die richtige Einfügeposition für den neuen Knoten bestimmt. Hierbei ist der Sortieralgorithmus zu beachten (aufsteigend oder absteigend etc.).
Wenn die richtige Position Stelle gefunden ist, wird ein neuer Knoten erzeugt. Der Zeiger des vorausgegangenen Knoten wird auf den neu eingefügten Knoten gesetzt und der Zeiger des eingefügten Knotens auf den nachfolgenden Knoten. Entsprechend wird bei einer beidseitigen verketteten Liste auch der Rückzeiger versetzt.

Abb.1: Einfügen eines Knoten

Das Entfernen eines Datenelements verläuft analog: Auffinden des gesuchten Elements, dann Zeiger versetzen und Element löschen. Auch hierbei muss insbesondere das Versetzen der Zeiger sorgfältig programmiert werden, um das Zerbrechen der Liste und damit Datenverlust zu vermeiden.

Vorgehensweise

Eine sortierte Liste kann mit unterschiedlichen Algorithmen zum Auffinden der passenden Einfüge- bzw. Löschposition implementiert werden.

Beim Durchlaufen der Liste wird nur ein einziger Suchzeiger benutzt. Zum Einfügen oder Löschen eines Elements muss dann jedoch ein temporärer Hilfszeiger verwendet werden, der die Adresse des folgenden Elements zwischenspeichert, bis die Operation abgeschlossen ist.

Auf den temporären Hilfszeiger kann verzichtet werden, wenn zwei Suchzeiger zum Durchlaufen der Liste benutzt werden. Sie laufen im Schrittabstand parallel und zeigen auf die benachbarten Elemente.

temporärer Hilfszeiger

Im folgenden Beispiel soll der Datensatz "3" in eine sortierte Liste eingefügt werden. Der Suchzeiger steht zu Beginn am Listenkopf.

Abb.2: Schritt 1

Zum Auffinden der richtigen Einfügeposition rückt der Suchzeiger elementweise weiter. Dabei wird über den next-Zeiger das jeweils folgende Element geprüft, ob es grösser oder kleiner ist als das Einzufügende.

Abb.3: Schritt 2

Wenn die Bedingung zutrifft, dann ist die richtige Einfüge-Position für das neue Element (3) gefunden. Nachdem das neue Element erzeugt wurde, kann der next-Zeiger des aktuellen Elements umgesetzt werden. Dies darf allerdings erst geschehen, nachdem ein temporärer Hilfszeiger (temp) die Adresse des nachfolgenden Elements gesichert hat. Dann kann der next-Zeiger des vorhergehenden Elements auf die Adresse des neuen Elements gesetzt werden und der next-Zeiger des neuen Elements auf die Adresse des nachfolgenden Element, die im temporären Hilfszeiger aufbewahrt worden ist. Der Hilfszeiger wird danach nicht mehr gebraucht.

Abb.4: Schritt 3

zwei ständige Zeiger

Beim Durchlaufen der Liste können alternativ auch zwei Zeiger eingesetzt werden. Am Beginn des Suchlaufs zeigen beide Zeiger zunächst gemeinsam auf den Listenkopf.

Abb.5: Schritt 1

Beim folgenden Suchvorgang zeigt der nachfolgende Zeiger auf den jeweils vorhergehenden Knoten (weil dessen next-Zeiger auf den neuen Knoten umgesetzt werden muss) und der Suchzeiger auf den aktuellen Knoten. So durchläuft der search-Zeiger die Liste knotenweise bis zum Ende und vergleicht dabei die Daten jedes Knotens mit den Daten des einzufügenden Knotens. Der last-Zeiger bleibt also immer eine Position zurück.

Abb.6: Schritt 2

Wenn die passende Position für den neuen Knoten in der sortierten Liste gefunden ist, dann wird der next-Zeiger des last-Knotens auf den neuen Knoten gesetzt und der next-Zeiger des eingefügten Knotens auf den search-Knoten. Damit ist der neue Knoten in der sortierten Liste an der richtigen Position verankert.

Abb.7: Schritt 3

Beispiele für sortierte Listen

Binäre Suchbäume
- AVL-Bäume
- Rot-Schwarzbäume
- Randomisierte Suchbäume
skip-Listen
Sparse Table

Übungen

Nehmen Sie sich einen der vorgestellten Suchalgorithmen und testen sie ihn mit verschieden Datentypen. Führen Sie für jeden Datentyp mehrere Durchläufe durch und messen Sie die Zeit. Nutzen Sie als Zeitangabe Nanosekunden um möglichst genau Ergebnisse zu bekommen.

Lösungen

Beispiels Lösung lineare Suche mittels Array

public class Search {

	private static final int runs = 1000; // Anzahl der Durchläufe
	private static final int valsCount = 32000; // Länge des Arrays
	private static final int val = 31999; // zu suchendes Element

	// verschiedene Datentypen
	private static int[] intVals = new int[valsCount];
	private static long[] longVals = new long[valsCount];
	private static double[] doubleVals = new double[valsCount];
	private static float[] floatVals = new float[valsCount];
	private static char[] charVals = new char[valsCount];
	private static short[] shortVals = new short[valsCount];
	
	public static void main(String[] args) {
		
		// Arrays befüllen
		for (int i = 0; i < valsCount; i++) {
			intVals[i] = i;
			longVals[i] = i;
			doubleVals[i] = i;
			floatVals[i] = i;
			charVals[i] = (char) i;
			shortVals[i] = (short)i;
		}

		// Zeitmessung für einzelne Datentypen
		// int
		long timeBefore = System.nanoTime();
		long index = 0;
		for (int i = 0; i < runs; i++) {
			index = sequentielleSucheArray(intVals, val);
		}
		System.out.println("Time int: " + (System.nanoTime() - timeBefore)
				/ 1000 + " result: " + index);
		// long
		timeBefore = System.nanoTime();
		for (int i = 0; i < runs; i++) {
			index = sequentielleSucheArray(longVals, val);
		}
		System.out.println("Time long: " + (System.nanoTime() - timeBefore)
				/ 1000 + " result: " + index);
		// double
		timeBefore = System.nanoTime();
		for (int i = 0; i < runs; i++) {
			index = sequentielleSucheArray(doubleVals, val);
		}
		System.out.println("Time double: " + (System.nanoTime() - timeBefore)
				/ 1000 + " result: " + index);
		// float
		timeBefore = System.nanoTime();
		for (int i = 0; i < runs; i++) {
			index = sequentielleSucheArray(floatVals, val);
		}
		System.out.println("Time float: " + (System.nanoTime() - timeBefore)
				/ 1000 + " result: " + index);
		// char
		timeBefore = System.nanoTime();
		for (int i = 0; i < runs; i++) {
			index = sequentielleSucheArray(charVals, val);
		}
		System.out.println("Time char: " + (System.nanoTime() - timeBefore)
				/ 1000 + " result: " + index);
		// short
		timeBefore = System.nanoTime();
		for (int i = 0; i < runs; i++) {
			index = sequentielleSucheArray(shortVals, val);
		}
		System.out.println("Time short: " + (System.nanoTime() - timeBefore)
				/ 1000 + " result: " + index);
	}

	private static int sequentielleSucheArray(int[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k) {
				// Wert gefunden
				return i;
			} else {
				if (k < a[i]) {
					// Wert nicht enthalten
					return -1;
				}
			}
		}
		// Wert nicht enthalten
		return -1;
	}

	private static int sequentielleSucheArray(long[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k) {
				return i;
			} else {
				if (k < a[i]) {
					return -1;
				}
			}
		}
		return -1;
	}

	private static int sequentielleSucheArray(double[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k) {
				return i;
			} else {
				if (k < a[i]) {
					return -1;
				}
			}
		}
		return -1;
	}

	private static int sequentielleSucheArray(char[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k) {
				return i;
			} else {
				if (k < a[i]) {
					return -1;
				}
			}
		}
		return -1;
	}

	private static int sequentielleSucheArray(float[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k) {
				return i;
			} else {
				if (k < a[i]) {
					return -1;
				}
			}
		}
		return -1;
	}
	
	private static int sequentielleSucheArray(short[] a, int k) {
		for (int i = 0; i < a.length; i++) {
			if (a[i] == k) {
				return i;
			} else {
				if (k < a[i]) {
					return -1;
				}
			}
		}
		return -1;
	}
}

Sortierte Folgen WS13-14

Inhaltsverzeichnis

Einleitung

Sortierte Folgen

Suchen in einer sortierten Folge

Algorithmisches Problem

Beispiele

Lineare Suche

Umsetzung in Java mittels Array

Umsetzung in Java mittels verketteter Liste

Analyse der linearen Suche

Annahmen zur Analyse der Laufzeit

Laufzeit in Abhängigkeit von der Eingabe

Laufzeit im schlimmsten Fall (worst case)

Idee zur Beschleunigung der Suche

Algorithmus binäre Suche

Umsetzung in Java

Laufzeit der binären Suche im worst case

Wie viele Durchläufe im worst case?

Vergleich Laufzeit Lineare Suche und binäre Suche

Einfügevorgang in einer sortierten Liste

Vorgehensweise

temporärer Hilfszeiger

zwei ständige Zeiger

Beispiele für sortierte Listen

Übungen

Lösungen

Suche