S. Spolwig

[Home | Algorithmen]

Sortieren ist das Anordnen einer Folge von Elementen nach einer vorgegeben Ordnung. Jedes Element hat einen für den Sortiervorgang erforderlichen Schlüssel (key), auf den die üblichen Vergleichsoperationen ( < , =, >) und deren Kombinationen anwendbar sind.

Man unterscheidet interne (im Arbeitsspeicher) und externe Sortierverfahren, wenn der Hauptteil der Daten während des Sortiervorgangs auf externen Datenträgern verbleibt. Typische interne Verfahren sind Bubblesort, Quicksort, Straight Insertion. Ein externes Verfahren ist z. B. Mergesort, bei dem der gesamte Datenbestand eines Magnetbandes mit zwei Hilfsbändern durch Zusammenmischen von sortierten Folgen zum Endergebnis kommt.

Grundsätzliche Strategien sind:

• Sortieren durch Austauschen
  Zwei benachbarte Element werden vertauscht, wenn sie nicht in der richtigen Reihenfolge stehen. Sie Folge wird vom 1. Element an durchlaufen, bis die Folge sortiert ist.
   

• Sortieren durch Auswählen
  Man ermittelt das kleinste Element und setzt es an die 1. Stelle usw.
  
  

• Sortieren durch Einfügen
  Unter der Annahme, dass die Folge bereits teilsortiert vorliegt, wird das Element an der richtigen Stelle (die natürlich gesucht werden muss) eingefügt.

Zum Testen der Sortieralgorithmen benutzten Sie das Programm Sort99, das Sie aus dem Gruppenordner kopieren. Das Programm ist voll funktionstüchtig bis auf die fehlende Sortiermethode. Das Programm hat dieselbe Klassenstruktur wie Such99.
Beim Klick auf den OK-Button erzeugt der Wortgenerator zufällig künstliche Wörter, mit denen die Stringliste gefüllt wird. Die Liste wird dann mit der üblichen Methode MaskeAktualisieren an die Listbox im Fenster übergeben und dort angezeigt.

Aufgabe:

1. Studieren Sie bitte uFensterFrm, damit Sie wissen, was und wo Sie etwas zu ergänzen haben.
   Wortliste als Unterklasse von StringListe ist unsere bekannte SListe, die jetzt mit speziellen Such- und Sortiermethoden erweitert wird.
   
   

2. Implementieren Sie die Listen-Methode Bubblesort1

procedure TWortListe.Bubblesort1;
(* ------------------------------------------------------------------ *)
(* Auftrag: lineares Sortieren durch systematisches Vergleichen aller *)
(*          Elemente und Tauschen mit dem nachfolgenden Element       *)
(* Vorher : Liste ist nicht leer                                      *)
(* Nachher: Liste ist aufsteigend sortiert                            *)
(* ------------------------------------------------------------------ *)

2. Ergänzen Sie das Programm dahingehend, dass die Anzahl der Vergleichsoperationen angezeigt wird.