Robert Sedgewick: Algorithmen

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


10. Digitales Sortieren



Übungen

  1. Vergleichen Sie für die Datei 001, 011, 101, 110, 000, 001, 010, 111, 110, 010 die Anzahl der von Radix Exchange benötigten Austauschoperationen mit der von Quicksort benötigten.
  2. Warum ist es bei Radix Exchange Sort nicht so wichtig, die Rekursion zu beseitigen, wie bei Quicksort?
  3. Modifizieren Sie Radix Exchange Sort so, daß führende Bits ausgelassen werden, die bei allen Schlüsseln identisch sind. In welchen Situationen würde sich das lohnen?
  4. Ist folgende Behauptung wahr oder falsch: Die Laufzeit von Straight Radix Sort hängt nicht von der Reihenfolge der Schlüssel in der Eingabedatei ab. Begründen Sie Ihre Antwort.
  5. Welche Methode dürfte für eine Datei, in der alle Schlüssel gleich sind, schneller sein, Radix Exchange Sort oder Straight Radix Sort?
  6. Ist folgende Behauptung wahr oder falsch: Sowohl Radix Exchange Sort als auch Straight Radix Sort betrachten alle Bits aller Schlüssel in der Datei. Begründen Sie Ihre Antwort.
  7. Worin besteht, abgesehen von dem zusätzlichen Bedarf an Speicherkapazität, der hauptsächliche Nachteil der Strategie, Straight Radix Sort auf die führenden Bits der Schlüssel anzuwenden und anschließend die Datei mit Insertion Sort endgültig zu ordnen?
  8. Wieviel Speicherplatz wird genau benötigt, um Straight Radix Sort mit vier Durchläufen auf N aus b Bits bestehende Schlüssel anzuwenden?
  9. Bei welchem Typ von Eingabedatei läuft Radix Exchange Sort am langsamsten ab (für sehr großes N)?
  10. Führen Sie für eine zufällige Datei, die aus 1000 Schlüsseln mit je 32 Bits besteht, einen empirischen Vergleich von Straight Radix Sort mit Radix Exchange Sort durch.


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