Streuwert-Tabellen
- Als Indexstruktur werden Streuwerttabellen verwendet um Datenelemente in einer großen Datenmenge aufzufinden
- Streuerttabellen zeichnen sich durch einen üblicherweise konstanten Zeitaufwand bei Einfüge- bzw. Entfernen-Operationen aus
- Die Größe M einer Streuwerttabelle sollte eine Primzahl sein, da bei nicht-Primzahlen beim Addieren eines Vielfachen von M zum Schlüsselwert der selbe Streuwert erzeugt werden kann → Kollision
Anwendung
- Zeichenketten können in ganzzahlen umgerechnet werden
- Diese können dann modular gestreut werden
Beispiel:
- Schlüssel seien Zeichenketten aus vier Großbuchstaben
H A N S 8 1 14 19 01000 00001 01110 10011 8*32^3 + 1*32^2 + 14*32^1 + 19*32^0 = 263635 263635 ≡ x (mod 101) → x = 25 Beim Rechnen mit langen Zeichenketten können Zahlen entstehen, die für die meisten Computer zu groß sind
- Rechentrick: Hornerschema (Beispiel: L05 – S. 44)
- Bei jeder Rechnung wird nur mit dem Rest modulo M weitergerechnet
Kollisionsbehandlung: getrennte Verkettung
- Für jede Tabellenadresse wird eine verkettete Liste angelegt, die alle Knoten enthält, deren Schlüssel auf diese Adresse abgebildet wurden.
Kollisionsbehandlung: offene Adressierung
- Voraussetzungen
- Maximale Anzahl der Elemente, die gespeichert werden sollen kann vorher ungefähr abgeschätzt werden
- genug zusammenhängender Speicher vorhanden
- Streuwerttabelle wird gleich als Datenfeld erzeugt
- Bei Kollisionen wird auf die freien Plätze in der Streuwert-Tabelle ausgewichen
Zusammenfassung: Streuwerttabellen
- Zwei Extrema
- Ohne Speicherbeschränkung, mit beliebig großen Streuwert-Tabellenkönnte jede Suche mit nur einem einzigen Speicherzugriff realisiert werden.
- Ohne Zeitbeschränkung könnte jede Suche mit nur minimalem Speicherplatz realisiert werden
- Mit Streuwerttabellen kann das Verhältnis zwischen diesen beiden Richtungen beliebig bestimmt werden.
- Durch Anpassung der Größe der Tabelle
Letzte Vorlesungseinheit: Fortgeschrittenes Sortieren
Insertionsort:
void insSort( vector<T>& vV, int ui, int oi ) {
int i(0), j(0); T tmp = T();
for( i=oi; i>ui; --i ) swap_if( vV[i-1], vV[i] );
for( i=ui+2; i<=oi; ++i ) {
j = i; tmp = vV[i];
while( tmp<vV[j-1] ) {
vV[j] = vV[j-1];
--j;
}
vV[j] = tmp;
}
}
Problem: Elemente, die sich in den ursprünglichen, unsortierten Daten weit entfernt vonihrer späteren, endgültigen Position innerhalb der sortierten Daten befinden, müssen mit vielen benachbarten Elementen einzeln vertauscht werden.
Lösung: Shellsort
- Elemente, die weit voneinander entfernt liegen, werden zuerst direkt vertauscht
- h-sortierte Daten: Daten werden h-sortiert genannt, wenn man durch Entnahme jedes h-ten Elements sortierte Daten erhält.
Beispiel: absteigend 3-sortierte Daten 25 830 67 17 320 55 14 288 49 11 245 33 9 170 24 6 143 21 4 99 16 25 830 67 17 320 55 14 288 49 11 245 33 9 170 24 6 143 21 4 99 16 25 830 67 17 320 55 14 288 49 11 245 33 9 170 24 6 143 21 4 99 16
- Beobachtung:
- h-sortiert man k-sortierten Daten, ist das Ergebnis sowohl h- als auch k-sortiert
Beispiel: Eine 1-Sortierung entspricht der Insertion Sort. Durch das Sortieren bei „Shell-Sort“ werden ungünstige Fälle aussortiert.
Implementierung
template<class T> void shlsrt( vector<T> vV, int ui, int oi ) {
int i(0), j(0), h(0), d(-1);
T tmp = T();
while( h <= (oi-ui+1)/9 ) h = (3*h)+1; // Startwert für h
for( ; h>0; h /= 3 ) {
while( ++d < h ) {
// kleinstes Element jeweils an den Anfang:
for( i=oi-d; i>=ui+h; i-=h ) swap_if( vV[i-h], vV[i] );
// sortieren:
for( i+=h; i<=oi; i+=h ) {
j=i; tmp = vV[i];
while( tmp < vV[j-h] )
}
} // "d-Schleife"
d = -1;
} // "h-Schleife"
}
Eigenschaften von Shellsort
- Leistungseigenschaften können nur ungenau beschrieben werden
- Niemand konnte den Algorithmus bis wirklich analysieren
- Hat keinen Worst-Case
- ist nicht abhängig von ursprünglichen Ordnung
- kein stabiles Sortierverfahren
- Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.
- sehr kurzes Programm und einfach zu implementieren