-
Der Insertion Sort ist langsam, weil nur benachbarte Elemente ausgetauscht werden. Wenn sich zum Beispiel das kleinste Element zufällig am Ende des Feldes befindet, so werden N Schritte benötigt, um es dorthinzubekommen, wo es hingehört. Shellsort ist einfach eine Erweiterung von Insertion Sort, bei dem eine Erhöhung der Geschwindigkeit dadurch erzielt wird, daß ein Vertauschen von Elementen ermöglicht wird, die weit voneinander entfernt sind.
...
mehr
-
Der Quicksort ist das am häufigsten verwendete Sortierverfahren, weil es sehr einfach zu implementieren ist. Er wurde 1960 von C.A.R. Hoare entwickelt und wurde seither von vielen Forschern untersucht.
Der große Vorteil besteht darin, daß er am Ort abläuft, und das für das sortieren von N Elementen im Durchschnitt nur N log N Operationen erforderlich sind, und daß er eine extrem kurze innere Schleife besitzt.
Der Nachteil besteht darin, daß er ...
mehr
-
Eine Verbesserung von Quicksort ergibt sich aus der Beobachtung, daß ein rekursives Programm stets sich selbst für viele kleine Teildateien aufruft, daher sollte es eine möglichst gute Methode verwenden, wenn es kleine Teildateien verarbeitet. Ein offensichtlich möglicher Weg, um das zu erreichen, besteht darin, den Test zu Beginn des rekursiven Programms in der Weise abzuändern, daß Insertion Sort aufgerufen wird. Wenn der Insertion Sort aufgeru ...
mehr
-
Eine sehr spezielle Situation, für die ein einfacher Sortieralgorithmus existiert, wenn eine Datei mit N Datensätzen viele verschiedene Zahlenschlüssel hat. Die Idee besteht darin, die Anzahl der Schlüssel mit jedem Wert zu ermitteln und dann die Ergebnisse der Zählung zu verwenden, um bei einem zweiten Durchlauf durch die Datei die Datensätze in die richtige Position zu bringen.
Hier wird ein Feld mit lauter Nullen angelegt und darüber di ...
mehr
-
key = 8000 byte 4 byte 10 byte
7 7 1
1 1 2
3 3 3
2 2 4
. . .
. . .
. . .
. . .
Hier arbeitet der Algorithmus indirekt (unter Verwendung eines Feldes von Indizes) mit der Datei und das Umordnen wird nachträglich vorgenommen.
1 2 3 4 ... 1 2 3 4 ...
7 1 3 2 ... 7 1 3 2 ... 1 2 3 7
1 2 3 4 ... 2 4 3 1 ...
Abb. 1 Abb. 2
Abb.1:
In der Mitte sind die zu ordnenden Zahlen: 7, 1, 3, 2 ...
mehr
-
Unter Suchen wird das Wiederauffinden von Information aus einer großen Menge zuvor gespeicherter Informationen verstanden. Normalerweise wird Information in Datensätzen gespeichert, die einen Schlüssel besitzen, nach dem gesucht wird. Das Ziel ist es, alle Elemente aufzufinden, deren Schlüssel mit dem Suchschlüssel übereinstimmt.
Das Suchen benötigt bestimmte Datenstrukturen, diese kann man einfach mittels Wörterbücher erklären. Im Wörterbuch ...
mehr
-
Die Daten werden in einem Feld gespeichert und neue Datensätze werden am Ende angefügt. Beim Suchen wird jedes Element des Feldes nach dem anderen durchsucht, bis die Suche erfolgreich war, oder das Ende des Feldes erreicht wird.
Die sequentielle Suche in einem unsortierten Feld benötigt N+1 Vergleiche für eine erfolglose Suche, und durchschnittlich ungefähr N/2 Vergleiche für eine erfolgreiche Suche.
Verwendet man ein sortiertes Fel ...
mehr
-
Diese stellt eine mögliche Verbesserung dar. Hier versucht man genauer zu erraten, wo sich das gesuchte Element befindet. Dies erinnert an die Suche in einem Telefonbuch, wo man eher vorne zu suchen beginnt, wenn der gesuchte Name mit einem B beginnt. Im Beispiel wird wieder nach der 13 gesucht:
Interpolationssuche erfordert für erfolgreiche aber auch für erfolglose Suche niemals mehr als lg[lg(N+1)] Vergleiche.
Die Interpolationssuche ...
mehr
-
Die Suchzeit kann gegenüber der sequentiellen Suche verringert werden, indem man ein sortiertes Feld durchsucht. Das Feld wird in zwei Hälften geteilt, und festgestellt in welcher Hälfte des Feldes sich der gesuchte Datensatz befindet. Diese Methode wird dann rekursiv angewandt, bis nur mehr ein Datensatz übrig ist. Dieser kann der gesuchte sein, oder den Datensatz mit dem gesuchten Schlüssel gibt es nicht. Im Beispiel wird nach der Zahl 13 gesuc ...
mehr
-
Die bis jetzt behandelten Algorithmen waren recht unkompliziert im Vergleich zum Löschen einzelner Elemente aus einem binären Suchbaum. Hier kommt es nämlich darauf an, wo sich der Knoten befindet bzw. wieviele Nachfolger er hat. Hierzu ein Beispiel:
. Am einfachsten ist das Löschen eines Knotens ohne Nachfolger (C, L, P), weil nur eine Verkettung gelöscht werden muß.
. Beim Löschen von Knoten mit nur einem Nachfolger (A, R, H, M) muß die ...
mehr
-
Wie bereits bekannt ist, kann man die Folge der Vergleiche des binären Suchens in einem binären Baum darstellen. Die Idee ist nun, die Daten in einem Baum durch Verkettung zu speichern. Der Vorteil gegenüber der binären Suche ist, daß die Datenstruktur immer leicht wartbar ist. Es ist einfach ein neues Element einzubinden und ohne kompliziertes Herumschieben von Daten ist immer eine sortierte Struktur vorhanden.
Sie ist eine der fundamentalste ...
mehr
-
Für viele Anwendungen benötigt man die Suchstruktur ausschließlich zum Suchen, und nicht zum Herumschieben von Datensätzen. Ein Beispiel wäre ein Feld mit allen Datensätzen mit Schlüsseln. Hier könnte man den Feldindex des Datensatzes suchen, der mit einem bestimmten Schlüssel übereinstimmt. So könnte man auch einen Datensatz mit einem bestimmten Index aus der Suchstruktur entfernen, ihn aber trotzdem noch im Feld behalten.
Ein Weg zur Indirek ...
mehr
-
Dieser Algorithmus behandelt in erster Linie die Platzreduzierung und erst in zweiter Linie behandelt er die Zeitreduzierung. Diese Technik heißt auch Kodierungsmethode.
Im allgemeinen haben Dateien einen hohen Grad an Redundanz. Die Verfahren, die wir untersuchen, sparen Platz da die meisten Dateien einen relativ geringen Informationsgehalt haben.
Einsparungen kann man bei einer Textdatei von 20% bis 50% haben, bei einer binären
Datei hat man ...
mehr
-
Man spricht hier von einem Lauf (run) dann, wenn sich lange Folgen sich wiederholender
Zeichen darstellt.
1. Methode bzw. Bsp.:
AAAABBBAABBBBBCCCCCCCCDABAAABBBBCCCD
Diese Zeilenfolge kann viel Kompakter kodiert werden, indem man die wiederholenden Zeichen nur einmal angibt und die Anzahl der Wiederholungen davor schreibt.
Also würde dann unser Bsp. kodiert so aussehen:
4A3B2A5B8CDABCB3A4B3CD
Bei einem Bitrast ...
mehr
-
Dieses Datenkompressionsverfahren spart beträchtlich Platz bei Textdateien.
Nehmen wir an wir wollen eine Zeichenfolge "ABRACADABRA" kodieren, und dieses mit dem herkömmlichen Verfahren des binären-Codes, bei einer Binärdarstellung mit Hilfe von 5 Bits zur
Darstellung eines Buchstabens.
Dann lautet die Bitfolge so:
0000100010100100000100011000010010000001000101001000001
Um diese zu dekodieren, nimmt man sich 5 Bits her und wandelt sie ...
mehr
-
Bei dem Erzeugen des Huffman-Codes kommt es in erster Linie darauf an wieviel Zeichen zu decodieren sind plus Leerzeichen. Nun ermittelt das folgende Programm die unterschiedliche Häufigkeit der Buchstaben eines Zeichenfeldes, und trägt sie dann in ein Feld count[0-26] ein.
Nun wieder ein Beispiel das wir kodieren , die Zeichenfolge lautet:
"A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBERS OF BITS".
Der erste Schritt ist der Aufbau ei ...
mehr
-
Bei der Implementation kommt es mehr darauf an den Huffman-Code richtig anzuwenden bzw.
die Vorausberechnung richtig zu rechnen, um daraus eine effiziente Kodierung zu bekommen.
Man sollte hier einen Trie finden der die Häufigkeit der Buchstaben berechnet oder Zeichen
verwendet, deren Häufigkeit in einem Pascal Programm auftretten z.B.: ; und dafür eine Bitfolge reserviert.
So ein Kodierungsalgorithmus kann mit Hilfe des Huffman Codes 23% E ...
mehr
-
Runlength: Abhängig von Zeichenfolge (häufig sind lange Folgen von selben Zeichen)
Hufman: Abhängig von Häufigkeiten (wenige Zeichen extrem häufig)
Beispiel für Runlength: 1
11
21
1211
111221
312211
Differential Encoding:
4,32 4,34 4,31 4,36 4,31
4,32 +0,02 -0,03 +0,05 -0,05
Pictureencoding:
Bild JPEG MPEG
22 MB 700 KB 170 KB
Predictive Encoding (Digitales Telefon):
Meßwert 202 304 398 500 599 704
Schätzung 200 300 400 500 ...
mehr
-
Bei Hashing (zerhacken) handelt es sich um eine Methode für die direkte Bezugnahme auf Datensätze in einer Tabelle. Dies erfolgt mit Hilfe einer Funktion, die direkt aus dem jeweiligen Schlüssel die Adresse des zugehörigen Datensatzes errechnet.
Wenn man weiß, daß die Schlüssel nur ganze Zahlen von 1 bis N sind, kann beispielsweise der Datensatz mit dem Schlüssel 5 an der Tabellenposition 5 gespeichert werden.
Hashing ist eine Verallgemeine ...
mehr
-
Benötigt wird eine Funktion, die Schlüssel (für gewöhnlich ganze Zahlen oder kurze Zeichenfolgen) in ganze Zahlen aus dem Intervall [0 ... M-1] transformiert, wobei M die Anzahl von Datensätzen ist, die in dem verfügbaren Speicher untergebracht werden kann.
Hierfür werden in der Literatur eine Vielzahl von Hash-Algorithmen vorgeschlagen. Eine der bekanntesten Funktionen ist das Divisionsrestverfahren.
Hier ist für M eine günstige Primzahl zu ...
mehr
