Sortieralgorithmen sortieren Zahlen oder Buchstaben nach deren natürlichen Reihenfolge bzw. dem Alphabet. Die Effizienz eines solchen Algorithmus kann bei hohen Datenbeständen  entscheidende Auswirkungen auf die einzusetzenden Ressourcen haben. Viele Unternehmen oder Organisationen arbeiten mit grossen Datenbeständen und benötigen zu deren Organisation effiziente Algorithmen.  Auch ganze Zeichenketten können sortiert werden, wenn man vorher eine lexikographische Ordnung vorgibt, wie z. B. bei dem ASCII-Zeichensatz.  Die Komplexität des Algorithmus wird mit dem Landau Symbol angegeben. Ein Algorithmus hat dann beispielsweise bei n zu sortierenden Elementen eine Laufzeit mit dem konstanten Grenzwert von Θ (für Theta) n * Log (n).  Das Landau Symbol Theta (Θ) bedeutet hier eine konstant gleich wachsende Funktion, also linear wachsend. Θ n* Log (n) ist dann ein effizienter Algorithmus: man bezeichent ihn als super-linear.  Die Laufzeit und der Ressourcenverbrauch des Suchalgorithmus, also die Effizienz, hängen auch vom Ausgangszustand der zu sortierenden Zeichenkette ab. Man unterscheidet zwischen Best Case, Average Case und Worst Case, wobei der  Worst Case ein strenger Maßstab für den Algorithmus ist.

Arten von Sortierverfahren 
Weitere Unterscheidungskriterien für Sortieralgorithmen sind, ob sie unabhängig von der Anzahl der Elemente in der Zeichenkette einen bestimmten Speicherraum allozieren (in-place oder in situ)  oder ob das nicht der Fall ist (out-of-place, ex situ). Stabile Sortieralgorithmen liefern als Ergebnis ganz sicher eine Zeichenkette in der vorgesehenen Reihenfolge, instabile können dies nicht garantieren.  Manche Sortierverfahren arbeiten bei vorsortierten Daten besser (adaptiv), bei manchen ist dies unabhängig vom Grad der Unordnung in der Zeichenkette (nicht adaptiv).

Einzelne Sortierverfahren 

1. Bubblesort:
Bubblesort ist ein stabiler, nicht rekursiver Algorithmus, der im Worst Case eine Komplexität von Θ (n ²) bzw. Θ (n ²)/2 hat. Bubblesort ist in-place und vergleicht immer zwei Nachbarn um sie im Falle einer  falschen Reihenfolge zu vertauschen. Dazu sind meistens mehrere Durchläufe notwendig, wobei die grösseren bzw. kleineren Zahlen wie Bubbles (Blasen im Wasser) nach oben steigen. Man bezeichnet auch ein Zahlenpaar, welches zu vertauschen  ist, als 'Bubble'.

2. Insertion Sort:
Insertion Sort ist ein stabiles, nicht rekursives Sortierverfahren, arbeitet in-place. Die Komplexität im Worst Case beträgt ebenso wie bei Bubble Sort Θ (n ²) bzw. Θ (n ²)/2. Insertion Sort  ist ein einfacher, wenig effizienter Sortieralgorithmus der jedoch gute Ergebnisse bei vorsortierten Zeichenketten oder bei wenig Elementen aufzuweisen hat, und leicht zu implementieren ist. Das eigentliche Finden der korrekten Einfügeposition  kann durch eine binäre Suche relativ effizient erfolgen, während die Verschiebe-Operationen auf dem Array, auf dem der Algorithmus oft arbeiten muss, weniger effizient sind. Man kann Insertion Sort vom Sortierprinzip  mit einem Stapel Karten vergleichen, die nacheinander aufgedeckt werden und entsprechend auf der Hand eingeordnet werden. Die Einfügeposition wird ermittelt, indem die einzufügende Karte nacheinander mit den auf der Hand  befindlichen Karten verglichen wird.

3. Heapsort
Heapsort ist ein nicht stabiles, nicht rekursives aber effizientes Sortierverfahren. Die Komplexität von Heapsort beträgt im Worst Case Θ (n * (log (n)). Heapsort ist eine Weiterentwicklung von  Selection Sort und arbeitet in-place. Die Daten müssen für Heap Sort in einem binären Heap vorliegen oder vorher in einen solchen überführt werden. Ein binärer Heap ist eine Datenstruktur, die man  wie eine Prioritätswarteschlange (priority queue) einsetzen kann. In einem binären Heap kann man Elemente in beliebiger Reihenfolge effizient und mit festgelegter Priorität in den Heap hineinlegen und stets das Element mit höchster Priorität entnehmen.  Die Priorität wird durch Schlüssel aufgeprägt. Bei einem Min-Heap bildet der kleinste Schlüssel die Wurzel des Baumes und alle Nachfolger sind grösser, bei einem Max-Heap ist es genau umgekehrt. Bei einem Array  ist für die zweite Hälfte des Array die Heap-Eigenschaft immer erfüllt, denn jeder Knoten in der zweiten Hälfte des Arrays entspricht im Heap einem Blatt und hat folglich keinen Nachfolgeknoten, dessen Wert grösser  sein kann als der eigene Wert. Um ein Array in einen Heap zu überführen werden alle vor der Array-Mitte liegenden Knoten nacheinander versickert, d.h. dass ein Knoten mit dem grösseren seiner nachfolgenden Knoten  vertauscht wird, falls dieser Grösser als er selber ist, bis es keinen Nachfolgeknoten mehr gibt, der grösser ist, und das Ganze wird solange fortgesetzt, bis das erste Element versickert wurde. Bei einem Max Heap nutzt der Sortieralgorithmus den Aufbau  des Max-Heap, bei dem der erste Knoten stets grösser ist als alle Nachfolgenden, also die Wurzel der grösste Knoten ist. Man vertauscht also den ersten Knoten (die Wurzel) mit dem letzten Element des Heap, so dass dann der grösste Wert  wunschgemäss hinten steht. Dann wird der Rest des Heap wieder in einen Max-Heap überführt, indem das erste Element versickert wird. Dann wird wieder die neue Wurzel getauscht, und zwar mit dem vorletzten Element usw.

4. Mergesort
Mergesort ist ein  stabiler, rekursiver Sortieralgorithmus. Komplexität ist im Worst Case Θ (n * (log (n)), bei Arrays auch Θ (n). Mergesort verwendet das Prinzip 'Teile und Herrsche' (Divide et Impera). Mergesort ist out-of-place. Das Sortierprinzip  von Mergesort geht folgendermaßen vor: eine zu sortierende Liste wird in kleinere Teil-Listen aufgeteilt, die jede für sich sortiert wird. Danach werden die Listen wieder zusammengeführt (to merge). Für Mergesort geeignet sind verkettete Listen,  so dass sich eine in-place Sortierung ergeben kann.

5. Quicksort:
Quicksort ist nicht stabil, rekursiv und in-place. Komplexität im Worst Case: Θ (n ²), im Average Case: Θ (n * (log (n)). Quicksort arbeitet wie Mergesort nach dem Teile  und Herrsche Prinzip: die Ausgangsliste wird in 2 Teil-Listen aufgeteilt. Dafür wird ein Pivotelement aus der Liste gewählt. Alle Elemente die kleiner sind als das Pivotelement kommen in die linke Teil-Liste, alle die grösser sind in die Rechte. Danach  werden die Teillisten in sich sortiert, mit demselben Verfahren, d.h. durch Aufruf von Quicksort. Quicksort ist deswegen auch rekursiv, weil es sich immer wieder selber aufruft.

1. Mit Hilfe eines Hashverfahrens kann auf unverschlüsselten Daten eine Prüfsumme ermittelt werden. Diese dient als Signatur, um beispielsweise die Authentizität einer Datei zu überprüfen. Aus der Signatur kann nicht auf die Datei geschlossen werden. 

Die Erzeugung zweier verschiedener Dateien mit identischer Signatur (Kollision) sollte praktisch unmöglich sein. Ein Hashverfahren welches dieses leisten soll ist beispielsweise SHA-1 oder MD5.   
2. FTP-Client Befehl: Der Client soll beim Empfangen und Senden ein Nummernzeichen (#) anzeigen.                                                   

Bei der Phonetischen Suche, die vor allem von Suchmaschinen verwendet wird, muss der Anwender sich nicht an die korrekte Schreibweise halten. Das System erkennt Schreibfehler und Abweichungen bzw. es bietet alternative Schreibweisen oder Wörter an. Als  Beispiel für eine solche Suchmaschine dient "Google". Schreibt man "nähmlich", antwortet Google u.a. mit : Meinten Sie: "nämlich".                                                       

Fehlertolerante Systeme oder Fehlertolerante Suchalgorithmen sind in der Lage, auftretende Fehler abzufangen und entsprechend, auch auf die Fehlermeldung abgestimmt, zu reagieren. Unvollständigkeiten  oder Fehler bei der Eingabe in ein Suchenfeld sollten dem Nutzer nicht einfach als 'error messages' quittiert werden. Eine mögliche Strategie für fehlertolerantes Suchen mit PHP und MySQL ist:

  1. Eine Datenbankabfrage sucht nach einem Stichwort im Klartext.

// (...)
$Titel_Stichwort="Mainboard";
$STRSQL_01="SELECT master.idmaster, master.titel, master.body
  FROM master WHERE master.titel = \"$Titel_Stichwort\"
Order by master.titel asc limit 0,1 ";
// (...)

  2. Liefert die MySQL-Abfrage keine Ergebnismenge wird das Suchwort mit einer "function" in ein phonetisches Suchmuster umgewandelt.
  2.1 Dies könnte in PHP mit dem Befehl soundex() geschehen oder
2.2 mit einer 'eigenen' buchstabenorientierten Substitutionsmethode:

  // Basierend aus dem Artikel "Schreibweisentolerante Suchroutine in dBase implementiert"
// c't - Magazin für Computertechnik 1988, Heft 10, Georg Wilde, Carsten Meyer

function meyer88($Substitution){

  // Alle Buchstaben werden zunächst in Großbuchstaben umgewandelt

$Substitution=strtoupper($Substitution);

// Buchstabenorientierte Substitutionsmethode:
// wandelt Buchstabenkombinationen in gleichlautendes Equivalent um

  $finde = array(

"SC","SZ","CZ","TZ","TS","DS","PH","PF",
"QU","UE","EU","AE","OE","KS","EI","EY",
"K","G","Q","Ü","I","J","ß","F","W","P","T");

  $ersetze = array(

"C","C","C","C","C","C","V","V",
"KV","Y","OY","E","Ö","X","AY","AY",
"C","C","C","Y","Y","Y","S","V","V","B","D");

  for($I=0;$I<27;$I++){
$Substitution = str_replace($finde[$I],$ersetze[$I],$Substitution);
// Doppelte Buchstaben werden entfernt
$Substitution = preg_replace('/(.)\1/', '$1', $Substitution);
}

  return $Substitution
}

3. Die nächste Datenbankabfrage sucht nun das neue Suchmuster. Denkbar ist ein relationales Datenbanksystem: Mit der Tabelle "master" und einer 1:n-Beziehung zu einer Detail-Tabelle: "slave" mit dem Feld: "phonetik"    ⇔ Bedingung hierfür ist, dass zuvor in der Tabelle ein mit demselben Algorithmus (meyer88) indexiertes Feld "phonetik" generiert wurde.

$Titel_Schlagwort_Phonetik=meyer88($Titel_Stichwort);

  $STRSQL_02="SELECT distinct master.idmaster, master.titel, master.body
FROM slave Right JOIN master ON
slave.idslave = master.idmaster
  WHERE slave.phonetik = \"$Titel_Schlagwort_Phonetik\"
Order by slave.phonetik asc";

4. Die Ergebnismenge der Schlagwörter aus $STRSQL_02 lassen sich nun auf mehrere Arten mit dem ursprünglichen Suchwort:  "$Titel_Stichwort" vergleichen.
⇒ In PHP gibt es hierfür zwei Methoden, um ein Maß für die Unterschiede zweier Wörter zurückzuliefern:
  similar_text() => Berechnet die Ähnlichkeit zweier Zeichenketten und
  levenshtein() => Die Levenshtein-Distanz wurde erstmalig 1965 von dem russischer Mathematiker Wladimir Iossifowitsch Lewenstein, als die "minimale Anzahl von Löschungen, Einfügungen und Ersetzungen" definiert, die ein Wort X in das Wort Y umwandelt.

                     

LZ77 ist ein Kompressionsformat, welches mit Präkodierung arbeitet. Bei der Präkodierung wird mit statistischen Abhängigkeiten gearbeitet.  Dabei werden Symbole aus einem Alphabet auf Symbole eines anderen Alphabets abgebildet. LZ77 (und LZ78) verwendet zur Präkodierung die wörterbuchbasierte Kodierung (Lauflängenkodierung oder Phrasencodierung).  Weitere Verfahren zur Präcodierung sind: Burrows-Wheeler-Transformation (Blocksortierung) oder Quadtree-Kodierung.  LZ77 wurde von Abraham Lempel und Jacob Ziv 1977 veröffentlicht. LZ77 und LZ78 bilden die Basis für die LZ-Algorithmen (LZX, LZW (Lempel-Ziv-Welch-Algorithmus), LZSS (Lempel-Ziv-Storer-Szymanski-Algorithmus),  LZMA (Lempel-Ziv-Markow-Algorithmus oder engl.: Lempel-Ziv-Markov Chain Algorithm (Markow-Kette)).                                                 

LZX ist ein Datenkomprimierungsalgorithmus der LZ77-Familie (Lempel-Ziv-1977) sowie ein Dateiarchivierungsformat.  LZX ist ursprünglich eine Programmiersprache in der OpenLaszlo Open Source Entwicklungsplattform. OpenLaszlo dient der  Entwicklung und Bereitstellung von Rich Internet Anwendungen (Rich Internet Applications). OpenLaszlo ist zertifiziert unter der CPL (Common Public License).  LZX wurde von Tomi Poutanen und Jonathan Forbes entwickelt. Forbes wechselte später zu Microsoft und nahm die Lizenz mit, so dass Microsoft heute Inhaber der LZX-Lizenz ist. Microsoft verwendet LZX u.a. bei dem  Dateiarchivierungsformat .cab (CAB-Dateiformat), vor allem bei der Installation von Microsoft- und Windows-Software (Service Packs, Updates und Patches). 

LZ77 Datenkompressionsalgorithmus 
LZ77 ist ein Kompressionsformat, welches mit Präkodierung arbeitet. Bei der Präcodierung wird mit statistischen Abhängigkeiten gearbeitet.  LZ77 wurde von Abraham Lempel und Jacob Ziv 1977 veröffentlicht. LZ77 (LZ78) wird auch LZ1 (LZ2) genannt. LZ77 und LZ78 bilden die Basis für die LZ-Algorithmen (LZX, LZW (Lempel-Ziv-Welch-Algorithmus), LZSS,  (Lempel-Ziv-Storer-Szymanski-Algorithmus),  LZMA (Lempel-Ziv-Markow-Algorithmus) oder engl.: Lempel-Ziv-Markov Chain Algorithm (Markow-Kette)).                                       

PKZip (Phil Katz' ZIP) ist ein Kompressionsprogramm, welches Daten in Archiven packen kann, damit weniger Speicherplatz benötigt wird.  Dies spart nicht nur Speicherplatz auf dem Datenträger, sondern es nützt auch, wenn Daten über das Internet oder ein Netzwerk verschickt werden sollen. Ein bekannter  Windows-Ableger ist WinZip, welches über eine benutzerfreundliche Oberfläche verfügt. Das Prinzip von PKZIP beruht auf der Verringerung von Redundanz, vor allem bei Texten und Grafiken.

Das Bulletin Board System und Archive 
Hintergrund für die Entwicklung von PKZip war der wachsende Verkehr von Dateien in den Mailboxen (BBS, Bulletin Board System) in den 80er Jahren und auch die  damals geringen verfügbaren Bandbreiten (Modem), so dass es sich lohnte, Dateien in gepackte Archive zu packen und dann zu versenden oder abzurufen.

PKArc und PKZip 
PKZip war dem damals beherrschenden Standard ARC bzw. PKArc (System Enhancement Associates) überlegen, so dass viele SysOps (BBS-Administratoren) zu PKZip wechselten.  Phil Katz (1962 - 2000) wollte PKZip einem grossem User-Publikum zugänglich machen und erklärtes es als Public Domain Software. PKZip war damit befreit von den Urheberrechten und galt als "gemeinfrei".

PKZip, PKWare, WinZip und Windows 
Leider machte Katz einen markttechnischen Fehler, als er das Microsoft Betriebssystem Windows nicht ernst genug nahm und erst 1996 eine Windows Version von PKZip auf den Markt brachte. Seine Firma PKWare kam anschliessend  im immer mehr von Windows beherrschten Markt ins Hintertreffen, da das Konkurrenzprodukt WinZip von Nicosoft sich bei Windows-Usern etablierte. PKZip konnte die verlorenen Marktanteile nie mehr zurückgewinnen und  WinZip machte das Rennen. 

Zip-Kompressionsalgorithmus Deflate und LZSS 
Das Zip-Kompressionsformat von Phil Katz arbeitet mit dem von Katz entwickelten Kompressionsalgorithmus Deflate.  Bei Deflate handelt es sich um einen verlustfreien Datenkompressionsalgorithmus der auf dem LZSS-Algorithmus (Lempel-Ziv-Storer-Szymanski-Algorithmus) basiert.