Programmieren, Algorithmen und Datenstrukturen 2 (Vorlesung 19)

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