Robert Sedgewick: Algorithmen

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


9. Quicksort



Übungen

  1. Implementieren Sie einen rekursiven Quicksort-Algorithmus, der für Teildateien mit weniger als M Elementen zu Insertion Sort übergeht, und bestimmen Sie empirisch den Wert von M, für den er bei einer zufälligen Datei mit 1000 Elementen am schnellsten abgearbeitet wird.
  2. Lösen Sie das obige Problem für eine nichtrekursive Implementation.
  3. Lösen Sie das obige Problem, wenn außerdem die Verbesserung mit Hilfe der Methode des mittleren von drei Elementen zur Anwendung kommt.
  4. Wieviel Zeit benötigt Quicksort ungefähr, um eine aus N gleichen Elementen bestehende Datei zu sortieren?
  5. Wie oft kann das größte Element während der Ausführung von Quicksort bewegt werden?
  6. Zeigen Sie, wie die Datei A B A B A B A unter Anwendung der zwei in diesem Kapitel vorgeschlagenen Methoden zerlegt wird.
  7. Wie viele Vergleiche muß Quicksort ausführen, um die Schlüssel E A S Y Q U E S T I O N zu sortieren?
  8. Wie viele »Marken«-Schlüssel werden benötigt, wenn Insertion Sort direkt aus Quicksort heraus aufgerufen wird?
  9. Wäre es sinnvoll, für eine nichtrekursive Implementation von Quicksort eine Schlange anstatt eines Stapels zu benutzen? Warum oder warum nicht?
  10. Schreiben Sie ein Programm, das eine Datei so umordnet, daß alle Elemente, deren Schlüssel mit dem Median übereinstimmen, sich an ihrem Platz befinden, mit kleineren Elementen auf der linken und größeren Elementen auf der rechten Seite.


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