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:
-
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.
-
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
*)
(* ------------------------------------------------------------------
*)
-
Ergänzen Sie das Programm dahingehend, dass die
Anzahl der Vergleichsoperationen angezeigt wird.
|