Robert Sedgewick: Algorithmen

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


8. Elementare Sortierverfahren



Übungen

  1. Geben Sie eine Folge von Operationen »Vergleichen /Austauschen« für das Sortieren von vier Datensätzen an.
  2. Welche der drei elementaren Methoden (Selection Sort, Insertion Sort oder Bubble Sort) läuft für eine bereits sortierte Datei am schnellsten ab?
  3. Welche der drei elementaren Methoden läuft für eine in umgekehrter Reihenfolge geordnete Datei am schnellsten ab?
  4. Prüfen Sie die Hypothese, daß Selection Sort das schnellste der drei elementaren Verfahren ist (für das Sortieren von ganzen Zahlen), gefolgt von Insertion Sort und dann von Bubble Sort.
  5. Geben Sie einen triftigen Grund an, weshalb es unzweckmäßig wäre, für Insertion Sort einen Marken-Schlüssel zu benutzen (abgesehen von dem, der bei der Implementation von Shellsort auftritt).
  6. Wie viele Vergleiche werden von Shellsort verwendet, um ein 7-Sortieren und anschließend ein 3-Sortieren der Schlüssel E A S Y Q U E S T I O N vorzunehmen?
  7. Geben Sie ein Beispiel an, das zeigt, weshalb 8, 4, 2, 1 keine gute Art und Weise wäre, eine Folge von Distanzen bei Shellsort zu beenden.
  8. Ist Selection Sort stabil? Wie steht es mit Insertion Sort und Bubble Sort?
  9. Geben Sie eine spezielle Variante des Distribution Counting für das Sortieren von Dateien an, in denen die Elemente nur einen von zwei Werten haben (entweder x oder y).
  10. Experimentieren Sie mit verschiedenen Folgen von Distanzen für Shellsort: Finden Sie eine, die für eine zufällige Datei aus 1000 Elementen schneller abläuft als die angegebene Folge.


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