Robert Sedgewick: Algorithmen

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


12. Mergesort



Übungen

  1. Implementieren Sie ein rekursives Mergesort, das für Teildateien mit weniger als M Elementen in Insertion Sort übergeht; bestimmen Sie empirisch den Wert von M, bei dem es für eine zufällige Datei aus 1000 Elementen am schnellsten abläuft.
  2. Führen Sie einen empirischen Vergleich des rekursiven und nichtrekursiven Mergesort für verkettete Listen mit N = 1000 durch.
  3. Implementieren sie ein rekursives Mergesort für ein Feld aus N ganzen Zahlen unter Verwendung eines Hilfsfeldes, dessen Größe weniger als N/2 beträgt.
  4. Ist folgende Behauptung wahr oder falsch: Die Laufzeit von Mergesort hängt nicht von dem Wert der Schlüssel in der Eingabedatei ab. Begründen Sie Ihre Antwort.
  5. Welches ist die kleinste Anzahl von Schritten, mit denen Mergesort auskommen könnte (bis auf einen konstanten Faktor genau)?
  6. Implementieren Sie ein nichtrekursives Bottom-Up-Mergesort, welches statt verketteter Listen zwei Felder verwendet.
  7. Geben Sie die ausgeführten Mischoperationen an, wenn das rekursive Mergesort zum Sortieren der Schlüssel E A S Y Q U E S T I O N angewandt wird.
  8. Geben Sie den Inhalt der verketteten Liste nach jeder Iteration an, wenn das nichtrekursive Mergesort zum Sortieren der Schlüssel E A S Y Q U E S T I O N angewandt wird.
  9. Versuchen Sie, ein rekursives Mergesort mit Benutzung von Feldern unter Verwendung von Dreiweg-Mischoperationen anstelle von Zweiweg-Mischoperationen zu realisieren.
  10. Überprüfen Sie für zufällige Dateien der Größe 1000 empirisch die in diesem Kapitel aufgestellte Behauptung, daß die Idee der Ausnutzung der »natürlichen« Ordnung in der Datei zu keiner Kosteneinsparung führt.


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