Binäre Suche

Binäre Suche – Die Idee

Die Binäre Suche verdankt ihren Namen der Überlegung, dass bei einem sortierten assoziativen Array (Key,Value) die Anzahl der benötigten Schlüsselvergleiche halbiert werden kann. Man nimmt den gegebenen Suchschlüssel und vergleicht dessen Wert mit dem Wert des mittleren Arrayelements. Wenn man Glück hat kann die Suche hier schon beendet sein. Wenn nicht wiederholt sich der Vorgang, entweder für die linke oder die rechte Hälfte des Arrays. Welches der beiden Segmente gewählt wird hängt davon ab, ob der gefundene Schlüsselwert größer oder kleiner als der Suchschlüssel war. Diesen Schritt wiederholt man solange, bis entweder das gesuchte Element gefunden wurde oder keine weitere Aufteilung mehr möglich ist. In diesem Fall konnte das gesuchte Element nicht gefunden werden.

Einfaches binäres Suchbeispiel

binaere suche beispiel

Beispielablauf einer binaeren Suche
Quelle: Algorithmen und Datenstrukturen
Pomberger,Dobler

Implementierungsbeispiel Java – interativ

	/**
	 * @param A 			Array mit den Elementen
	 * @param searchKey 	gesuchter Schlüssel
	 * @param lr 			Linker Rand
	 * @param rr 			Rechter Rand
	 * @return 				Index des gefundenen Schlüssel, ansonsten -1
	 */
	public static int binaereSuche(int[] A, int searchKey, int lr, int rr){

		while(lr<=rr){
			int mitte = (lr + rr)/ 2;

			if (A[mitte] == searchKey) return mitte;
			if (A[mitte] > searchKey) rr= mitte-1;
			if (A[mitte] < searchKey) lr= mitte+1 ;
		}

		return -1;
	}

Implementierungsbeispiel Java – rekursiv


	/**
	 * @param A 			Array mit den Elementen
	 * @param searchKey 	gesuchter Schlüssel
	 * @param lr 			Linker Rand
	 * @param rr 			Rechter Rand
	 * @return 				Index des gefundenen Schlüssel, ansonsten -1
	 */
	public static int binaereSucheRekursiv(int[] A, int searchKey, int lr, int rr){

		if(lr > rr) return -1;
		int mitte = (lr + rr) / 2;

		if (A[mitte] == searchKey)
			return mitte;
		if (A[mitte] > searchKey)
			return binaereSucheRekursiv(A, searchKey, lr, mitte-1);
		if (A[mitte] < searchKey)
			return binaereSucheRekursiv(A, searchKey, mitte+1, rr);

		return -1;
	}

Erfahrungen mit der Komplexität

Um in einem Array mit i Einträgen ein Element zu durchlaufen werden maximal [log2 n] Schritte benötigt. Somit liegt die Komplexität innerhalb der Klasse O(log n) was prinzipiel ein erstrebenswertes Laufzeitverhalten ist.

  1. Implementierung der binären Suche in Java und C: http://de.wikipedia.org/wiki/Binäre_Suche
  2. Binäre Suche im Java SDK: http://java.sun.com/javase/
  3. Siehe auch: http://hurm-it.de/blog/non-web-coding/quicksort/
Veröffentlicht unter Algorithmen, Java, C# und Co. | Verschlagwortet mit , , | Hinterlasse einen Kommentar

QuickSort

Quicksort (von englisch quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (lat. Divide et impera!, engl. Divide and conquer) arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt[1] und seitdem von vielen Forschern verbessert. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack).

(Quelle: Wikipedia – http://de.wikipedia.org/wiki/Quicksort)

 

QuickSort hat gegenüber anderen Sortieralgorithmen den Vorteil, dass er kein zusätzliches Hilfsarray benötigt, in dem die Daten stehen (im Gegensatz zu bspw. MergeSort). Das Aufteilen erfolgt so, dass man mit Hilfe einer Zeigervariable “i” am Anfang des zu sortierenden Arrays startet und erst wieder bei einem Arrayelement A[i], welches größer als das Pivotelement ist, stoppt. Parallel arbeitet der Zeiger j vom gegenüberliegenden Ende des Arraysegments aus nach links und hält bei allen Elementen A[j], die kleiner als das Pivotelement, sind. Haben beide Zeiger i und j einen Kandidaten gefunden, werden A[i] und A[j] miteinander vertauscht und der Vorgang beginnt erneut.

Beispielimplementierung Java

public static void quickSort (int[] A, int al, int ar){

if(al<ar){
 int pivot = A[al], // 1. Element als Pivotelement
 i=al, j=ar+1; // Aufspalten:

 while(true){ 
  while (A[++i] < pivot && i<ar){}
  while (A[--j] > pivot && j>al){}

  if (i<j) tausche(A,i,j);
  else break;
 }

 tausche(A,j,al);
 quickSort(A,al,j-1);
 quickSort(A,j+1,ar);
 }
}

public static void tausche(int[] A, int i, int j){
   int t = A[i]; 
   A[i] = A[j]; 
   A[j]=t;
}

Laufzeitverhalten von QuickSort

Gängig zur Beurteilung eines Algorithmus bzw. dessen Laufzeitverhaltes ist die Best-Worst-Mean Betrachtung. Dazu muss zunächst die theoretisch maximale und minimale Laufzeit des Algorithmus ermittelt werden. Im Falle von QuickSort ist der günstigsts denkbare Fall, dass das Pivotelement ungefähr 2 gleich große Teilesegmente erzeugt. Hierfür ergibt sich eine O(n*log(n)) Komplexität.

Diese Komplexität gilt bei QuickSort auch annähernd für der Mean-Case wenn man davon ausgeht, dass das Pivotelement(bei korrekter Auswahl) im Durchschnitt aller Fälle die Segmente ungefähr gleich aufteilt.

Der Worst-Case tritt bei QuicksSort dann auf, wenn das Pivotelement sich entweder am Anfang oder am Ende des Arrays befindet. Dadurch wird die Liste bei jedem Rekursionsdurchlauf nur jeweils um 1 Element verschoben. Das führt im Schlimmsten aller Fälle zu einer quadratischen Komplexität O(n²).

QuickSort bei der Arbeit

Quicksort

Quicksort animation Quelle: Wikipedia.org

Veröffentlicht unter Java, C# und Co. | Verschlagwortet mit , , , | Hinterlasse einen Kommentar

Sitemap – Inhaltsverzeichnis für die Website

Etwas sollte bei keiner Website fehlen: ein Inhaltsverzeichnis, im Web genannt Sitemap. Ähnlich wie bei einem Buch, hilft sie dem User schnell einen Überblick über die Inhalte der Website zu erlangen. Prizipiell gibt es dabei 2 herangehensweisen: manuell oder automatisch. Manuell bedeutet, ich erstelle einmal eine hardcodierte Webseite, auf der meine diversen Unterseiten jeweils verlinkt werden. Dieses Verzeichnis muss aber jedes mal, wenn sich irgendwo etwas am Inhalt verändert, eigenhändig angepasst werden. Viel bequemer ist die Sitemap automatisch, durch ein Skript oder ähnliches, aktualisieren zu lassen. Der nachfolgende Beitrag soll dem Leser die Idee hinter Sitemaps verdeutlichen, die verschiedenen Sitemap-Typen erklären und dabei helfen, eine Sitemap für die eigene Homepage zu erstellen.

Die Sitemap ist im Grunde ein Inhaltsverzeichnis fürs WWW. Eine gelungene Sitemap bietet den Besuchern alle relevanten Informationen, über die der Website zugrundeliegende Struktur. Wie bei jedem guten Buch ist sie die erste Anlaufstelle wenn es darum geht, den Content zu umreißen. Neben den klassischen Linkmaps gibt es weitere Verzeichnisarten wie beispielsweise alphabetische Indizes oder Keyword Clouds. Beide erfüllen im Kern die gleichen Funktionen, wobei letztere vor allem in der Bloggerszene vertreten ist.

 

Aufbau einer Sitemap

Generell gilt, die Sitemap sollte sich am Aufbau der Website orientieren. Nicht geeignet sind z.B. eine bestehende Unternehmensorganisation oder geografische Faktoren. Derartiges Wissen ist zwar innerhalb des Unternehmens sehr wichtig, trägt aber an dieser Stelle nicht gerade zur Übersichtlichkeit bei. Site von Hurm IT Blog Als kleines Beispiel verwende ich diesen Blog. Um Strukturen abzubilden, bieten sich besonders die bereits bestehenden inhaltlichen Kategorien bzw. Gruppierungen an. Sie vermitteln zunächst einen groben Umriss des Inhalts. Bei entsprechend großen Seiten werden die entstehenden Listen schnell lang, womit eine adequate Gliederung sehr wichtig wird. Ziel sollte dabei sein, die vorhandenen Informationen möglichst leicht verständlich darzustellen, damit jeder Besucher sofort die Seite überblicken kann.

 

Um den Überblick zu erleichtern, darf es letztlich an einer grafisch ansprechenden Darstellung nicht mangeln.

 

 

Gestaltungsalternativen für eine Sitemap

Natürlich sind hier der Fantasier keine Grenzen gesetzt. Einige Dinge sollte man jedoch beachten. Zum einen sollten hierachriche Zusammenhänge, z.B. zwischen Kategorie und Artikel, auch dementsprechen dargestellt werden. Zum anderen sollten vorzugweise ungeordnete Listen <ul> <li... ...="" ul=""></li...> verwendet werden. Verschachtelte, ungeordnete Listen eignen sich besonders gut zur Visualisierung von hierarchien Strukturen.Es folgen nun einige Stylingvarianten zum freien Weiterverwenden:

 

SlickMap CSS: Kostenlose CSS Library speziell für ungeordnete HTML-Listen – Download  | View Demo

CSS Sitemap System : Ist ein weiteres komplettes Stylingkonzept für Sitemaps – Download  | View Demo

Gutes Sitemap Styling Tut: Sehr schönes Sitemap Styling Tut mit praktischen Beispielen – Homepage besuchen

Veröffentlicht unter HTML, PHP, Webdesign | Verschlagwortet mit , , , | Hinterlasse einen Kommentar