Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


13. Externes Sortieren



Übungen

  1. Beschreiben Sie, wie Sie externes Auswählen realisieren würden: Finde das k-größte Element in einer aus N Elementen bestehenden Datei, wobei N viel zu groß ist, als daß die Datei im Hauptspeicher Platz finden würde.
  2. Implementieren Sie den Replacement Selection Algorithmus und benutzen Sie ihn dann zur Überprüfung der Behauptung, daß die erzeugten Sequenzen ungefähr doppelt so groß sind wie der Umfang des internen Speichers.
  3. Was ist das ungünstigste Ereignis, das eintreten kann, wenn Replacement Selection zum Erzeugen von Anfangssequenzen in einer aus N Datensätzen bestehenden Datei angewandt wird und dabei eine Prioritätswarteschlange der Größe M benutzt wird, wobei M < N gilt?
  4. Wie würden Sie den Inhalt einer Platte sortieren, wenn kein anderes Speichermedium (außer dem Hauptspeicher) zur Verfügung stünde?
  5. Wie würden Sie den Inhalt einer Platte sortieren, wenn nur ein Band (und der Hauptspeicher) zur Verfügung stünden?
  6. Vergleichen Sie das ausgeglichene Mehrweg-Mischen mittels vier und sechs Bändern mit dem Mehrphasen-Mischen bei der gleichen Zahl von Bändern für 31 Anfangssequenzen.
  7. Wie viele Phasen benötigt das Mehrphasen-Mischen mit fünf Bändern, wenn mit vier Bändern begonnen wird, auf denen sich am Anfang 26, 15, 22 und 28 Sequenzen befinden?
  8. Gehen Sie davon aus, daß die 31 Anfangssequenzen bei einem Mehrphasen-Mischen mit vier Bändern jeweils einen Datensatz lang sind (mit einer anfänglichen Verteilung 0, 13, 11, 7). Wie viele Datensätze sind in jeder der Dateien enthalten, die an der letzten Operation des Dreiweg-Mischens beteiligt sind?
  9. Wie sollten kleine Dateien in einer Implementation von Quicksort behandelt werden, die für eine sehr umfangreiche Datei auf einem virtuellen Speichersystem ablaufen soll?
  10. Wie würden Sie eine externe Prioritätswarteschlange organisieren? (Entwickeln Sie insbesondere einen Weg, um die insert- und remove-Operationen aus Kapitel 11 zu unterstützen, wenn die Anzahl der Elemente in der Prioritätswarteschlange so anwachsen könnte, daß diese nicht mehr im Hauptspeicher Platz finden würde.)


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]