PÜ 13: Felder, Such- und Sortierverfahren

1. Einführung - Szenario
  2. Aufgabenstellung
  3. Algorithmisch-programmiertechnische Grundlagen
       3.1. Arrays und Stringlisten
       3.2. Arbeit mit dem Zufallsgenerator
       3.3. Sequentielles Suchen
       3.4. Algorithmen von Sortierverfahren
             3.4.2. Sortieren durch Austauschen
             3.4.3. Quicksort
       3.5. Effizienzvergleich der Sortieralgorithmen

1. Einführung - Szenario

"Wer Sortieralgorithmen programmieren kann, beherrscht das kleine Einmaleins der Programmierkunst!"

Diese These ist nicht unumstritten, weil etliche das Programmieren Lehrende meinen, das kleine Einmaleins ginge noch viel viel weiter. Andererseits hat so mancher von diesen (mich eingeschlossen) seine liebe Not, wenn er beispielsweise "Quicksort" aus dem Stegreif in Programmiersprache niederschreiben soll...

Wie dem auch sei, in der Arbeit mit Schülern bieten sich Sortierverfahren immer wieder an, um Kenntnisse zu algorithmischen Grundstrukturen zu bündeln und, ohne dass dies aufgesetzt wirkt, mit Aspekten der theoretischen Informatik (z.B. aus der Komplexitätstheorie) zu verquicken.

Außerdem zeigt ein Blick in die Geschichte der Rechentechnik, dass neben der Automatisierung des Rechnens an sich vor allem der Wunsch nach Beherrschung und möglichst schneller Bearbeitung größerer Datenmengen eine Haupttriebkraft der Entwicklung automatisierter Datenverarbeitung darstellt.
Denken wir nur an Hermann Hollerith, der mit der Entwicklung eines Lochkartensystems die Bevölkerungszählung der USA von 1890 revolutionierte, wodurch deren Auswertungszeit von vorausgesagten zehn Jahren auf damals sensationelle sechs Wochen reduziert werden konnte.

Vorauszusetzendes:

Die Schüler kennen die algorithmischen Grundstrukturen Sequenz, Alternative und Zyklus und sind in der Lage, diese zur Lösung einfacher Problemstellungen miteinander zu kombinieren bzw. zu verschachteln.
Kenntnisse zum Datentyp Zeichenkette sowie Fertigkeiten bezüglich Zugriff und Manipulation einzelner Elemente der Kette sollten im Sinne einer Propädeutik zu Feldzugriffen und -operationen hinreichend gefestigt vorliegen.

Projektverlauf:

Anhand einer vorgegebenen Programmoberfläche werden die Schüler mit der komplexen Problemstellung konfrontiert und diese alsdann in überschaubare Einzelaufgaben (Teilprobleme) gegliedert. Die so entstandene Aufgabenfolge bestimmt dann den Unterrichtsverlauf über mehrere Stunden, wobei die Stoffauswahl und -vermittlung sich stets dem zu lösenden Teilproblem unterordnet.

Seitenanfang

2. Aufgabenstellung

Gegeben ist die abgebildete Programmoberfläche, die grob gesehen aus einem TabbedNotebook mit drei Registerseiten und einer ListBox besteht.

Page1: Belegung der ListBox mit Eingabewerten

Über Button1Click (Zahl anfügen) soll ein in Edit1 einzutragender Zahlenwert der Stringliste von ListBox1 hinzugefügt werden. Button3Click (Lösche) soll die Stringliste vollständig leeren. Grundlagen: TListBox - das Windows-Listenfeld   Das Ereignis Button2Click (Start) soll die Belegung der ListBox mit einer festzulegenden Anzahl von Zufallszahlen realisieren. Die Größe der einzelnen Zufallszahlen soll zwischen Null und einer einzugebenden Obergrenze liegen. Es ist abzusichern, dass nicht mehr als 5000 Zufallszahlen erzeugt werden. Grundlagen: Arbeit mit dem Zufallsgenerator

Page2: Sequentielle Suche nach Minimum und Maximum

Gesucht ist ein Algorithmus zur Suche des Minimums bzw. Maximums in einer Liste mit n Elementen. Neben den Werten von Min / Max ist auch deren Position in der Liste zu ermitteln und anzuzeigen (Voraussetzung für Sortierverfahren!). Sollte das Minimum bzw. Maximum unter den Listenelementen mehrfach vorhanden sein, ist nur die Position des ersten Auftretens zu speichern. Grundlagen: Sequentielles Suchen   Die Suchalgorithmen sind in das Programm zu implementieren und mit verschiedenen Belegungen zu testen, ggf. zu korrigieren. Beachte: Das Windows-Listenfeld enthält eine Stringliste. Damit also nicht das "alphabetische" Minimum bzw. Maximum ermittelt wird, müssen bei Vergleichsoperationen die Listenelemente in ein Zahlenformat konvertiert werden (z.B. mit der Funktion StrToInt).

Page3: Sortieralgorithmen und deren Effizienz

Das Sortieren der ListBox über direkte Zugriffe auf die Stringliste ist zwar möglich, dauert aber durch deren interne Datenstruktur und notwendige Typkonvertierungen schon bei relativ geringen Listengrößen unerträglich lange. Daher ist es notwendig, die Daten der Stringliste zunächst in ein Zahlenfeld zu transformieren und nach dem Sortiervorgang die geordneten Feldelemente wieder als Stringliste darzustellen.   a) Machen Sie Sich (falls nötig) mit den Datentyp "ARRAY" vertraut und stellen Sie Gemeinsamkeiten und Unterschiede zwischen Arrays und ListBox-Komponenten heraus! Grundlagen: Arrays und Stringlisten   b) Deklarieren Sie im Programm als globale Variable ein Feld für 5000 ganze Zahlen. Bereiten Sie danach die Prozedur Button6Click (Sortieren durch Austauschen) für das Sortieren vor, indem Sie die Transformationsalgorithmen Stringliste => Zahlenfeld und Zahlenfeld => Stringliste implementieren! Grundlagen: Datentransfers zwischen Stringlisten und typisierten Feldern    Anhand des altbewährten Programms sortiere.com (Download als Zip hier möglich) sollen die Algorithmen wesentlicher Sortierverfahren erkannt und verbalisiert werden. Schreiben Sie die Algorithmen so kurz wie möglich und so präzise wie nötig auf, so dass eine x-beliebige Person anhand Ihres Textes eine Menge von 10 bis 15 Zahlenkärtchen algorithmisch fehlerfrei nach dem jeweiligen Verfahren sortieren kann. zwei Beispiele: Sortieralgorithmen    a) Für das Sortieren durch Austauschen sind Struktogramm und Delphi-Quelltext gegeben. - Implementieren Sie den Algorithmus in Ihr Programm unter dem entsprechenden Button-Click-Ereignis. - Ergänzen Sie den Algorithmus, so dass die Anzahl der Vergleiche und Vertauschungen über Variablen mitgezählt wird und eine Ausgabe erfolgt. b) Der Algorithmus für das Verfahren "Bubble-Sort" ist in Struktogrammform zu entwerfen und danach in das Programm zu implementieren. Verfahren Sie weiter wie unter a)! c) Der Quicksort-Algorithmus liegt in verbaler Form und auch als "einbaufertiger" Quelltext vor. - Vollziehen Sie den verbalen Algorithmus an der Struktur des Quelltextes nach und beachten Sie dabei die Schachtelung der Prozeduren (farbige Markierung)! - Kopieren Sie den Quelltext über die Zwischenablage in Ihr Programm und passen Sie diesen den Gegebenheiten Ihrer Oberfläche an (Komponenten-Bezeichner, Variablen etc.)!    Für die nachfolgend durchzuführenden Effizienzvergleiche können Sie Ihr eigenes Programm oder aber die downloadbare Version feldsort.exe nutzen.    a) Lassen Sie verschieden große Felder aus Zufallszahlen sortieren und füllen Sie folgende Tabelle aus:   Anzahl der zu sortierenden Elemente Sortieraufwand mit:    500 1000 2000 3000 4000 5000 - Sort. durch Austauschen   - Bubble-Sort   - Quicksort   Hinweis: Nach erfolgtem Sortieren muss die das Feld repräsentierende ListBox zunächst geleert und danach wieder mit neuen Zufallswerten in entsprechender Anzahl gefüllt werden! Ansonsten entstehen unrealistische Ergebnisse.     b) Übertragen Sie die Tabelle in ein Kalkulationsprogramm und stellen Sie den Sortieraufwand in Abhängigkeit der Feldgröße für alle drei Verfahren in einem Liniendiagramm dar! Beurteilen Sie die Effizienz der untersuchten Sortierverfahren!     c) Angenommen, ein Rechner benötige zum Sortieren von 5000 Elementen durch Austauschen 1 Minute. - In welcher Zeit wäre das gleiche Feld mittels Quicksort sortiert? - Wie lange würde der Sortiervorgang für 1 Million Elemente jeweils mit Sortieren durch Austauschen bzw. Quicksort dauern? Grundlage: Berechnung des Sortieraufwandes

Seitenanfang

3. Algorithmisch-programmiertechnische Grundlagen

3.1. Arrays und Stringlisten

Ziele:

Kennen lernen des Datentyps Feld (Reihung) zunächst in eindimensionaler Ausprägung, Nutzung des Windows-Listenfeldes (TListBox) zur Visualisierung der E/A-Funktionen von Feldern.

 

Bearbeitung größerer Datenmengen
Datentyp Feld (ARRAY) für Operationen mit den Daten z.B. Suchen, Sortieren	Daten- transfer	Komponente TListBox zur Visualisierung der Ein- und Ausgabefunktionen

 

Der Datentyp Array (Feld, Reihung)

Begriff:	Ein Datenfeld ist eine Reihung einer bestimmten Anzahl zusammengehörender Daten gleichen Typs, die unter einer einzigen Variablen abgespeichert sind.
Beispiele:	a) Feld aus 100 ganzen Zahlen namens z Feldbezeichner[Index]: z[1] z[2] z[3] z[4] ... z[100] Wert: 74 18 2 61 ... 23 b) Feld aus 15 Zeichenketten namens pers Feldbezeichner[Index]: pers[0] pers[1] ... pers[14] Wert: 'Max' 'Paul' ... 'Felix'
Deklaration:	zu a)  var z: ARRAY[1..100] OF Integer; zu b)  var pers: ARRAY[0..14] OF String[20];
Zugriffe:	Wie auf andere Variablen kann unter Verwendung des Index auch auf die Elemente eines Feldes  mittels Wertzuweisung lesend bzw. schreibend zugegriffen werden. z.B. x := z[7]; Edit5.Text := IntToStr(z[22]);        pers[1] := 'Paul'; Label8.Caption := pers[14];

 
TListBox - das Windows-Listenfeld

Diese Komponente dient zur Aufnahme und Anzeige einer Stringliste und ist damit auch zur Visualisierung eindimensionaler Datenfelder geeignet. Wichtige Eigenschaften: Items: Liste der Strings, die in der ListBox gespeichert sind. Items.Count: Anzahl der in der Stringliste enthaltenen Elemente. Itemindex: Ordinalzahl des ausgewählten (markierten) Elementes der Stringliste. Das erste Listenelement (im Bsp. '389') steht immer an der Position 0! (ListBox1.Items[0]). Folglich ergibt sich der Index des letzten Elementes aus ListBox1.Items.Count-1.

Beispiele:

Anzeige des Index des markierten Listenelementes über Label1: Label1.Caption := IntToStr(ListBox1.ItemIndex);   Anzeige des letzten Elementes der ListBox über Edit5: Edit5.Text := ListBox1.Items[ListBox1.Items.Count-1]; Vereinfachung der Beispiele 1 und 2 mittels With-Operator: with ListBox1 do begin   Label1.Caption := IntToStr(ItemIndex);   Edit5.Text := Items[Items.Count-1]; end; {of with}

 
Datentransfer zwischen Stringlisten und typisierten Feldern

Diese Algorithmen beinhalten Zählschleifen (vom ersten bis zum letzten Element tue ...) und falls es sich nicht um ein Feld aus Zeichenketten handelt auch Funktionen zur Typumwandlung.
Da Stringlisten mit dem Index 0 beginnen, sollten die entsprechenden Felder auch von 0 bis Maxindex deklariert werden, wobei der Maxindex der Anzahl der Listenelemente - 1 entspricht.

Beispiel:

Es existiere eine ListBox1 vom Typ TListBox und ein zfeld (Feld ganzer Zahlen) sowie eine ganzzahlige Variable namens maxindex. a) Werte der ListBox in das Feld überführen: maxindex := ListBox1.Items.Count - 1; for i := 0 to maxindex do   zfeld[i] := StrToInt(ListBox1.Items[i]); b) Feldelemente in der ListBox anzeigen: ListBox1.Clear; for i := 0 to maxindex do   ListBox1.Items.Add(IntToStr(zfeld[i]));

Seitenanfang

3.2. Arbeit mit dem Zufallsgenerator

Computer und Zufall

Computer und "echter" Zufall sind so unvereinbar wie Feuer und Wasser. Macht es dem Menschen keinerlei Mühe, z.B. eine Zufallszahl zwischen 1 und 10 anzusagen, so gerät der Rechner hier an seine Grenzen - Computer kennen eben keinen Zufall, ihre inneren Abläufe sind determiniert!

Allerdings gibt es Algorithmen, die bei mehrfacher Ausführung eine Folge von Zahlen erzeugen, die viel mit einer zufällig (z.B. durch Würfeln) erzeugten Zahlenfolge gemeinsam haben. Man nennt jeden Algorithmus dieser Art einen Zufallsgenerator. Die Zahlen, die erzeugt werden, heißen Zufallszahlen (genauer: Pseudo-Zufallszahlen, da tatsächlich nicht etwa gewürfelt, sondern gerechnet wird).
Jeder Zufallsgenerator benötigt eine Startzahl, mit deren Hilfe er die erste Zufallszahl berechnen kann, danach wird die zweite berechnet usw.  Startete man nun mehrfach mit derselben Zahl, so würde stets dieselbe "Zufallsfolge" erzeugt und der Rechner wäre schnell durchschaut. Beginnt man jedoch mit verschiedenen Startzahlen, so erscheinen völlig verschiedene Zufallsfolgen.

Die folgende Rechenvorschrift stellt einen einfachen Zufallsgenerator dar:

Xn+1 = (Xn * 473 + 577) MOD 2551;
0 <= X0 <= 2550 (Startwert beliebig auswählbar)

mit X0 = 123   entsteht die Zufallsfolge: 83, 1571, 1319, 2020, 512, 408, 2236, ... und
mit X0 = 550   entsteht die Zufallsfolge: 525, 1455, 22, 779, 1700, 1112, 1047, ...

Zufallsgeneratoren existieren in den meisten imperativen Programmiersprachen als vordefinierte Funktion und sind intern sicherlich weit komplizierter aufgebaut, als das angeführte Beispiel.

Der Zufallsgenerator in Pascal:

Der Startwert braucht hierbei nicht vom Nutzer eingegeben zu werden, er wird vielmehr aus der Systemzeit des Rechners gebildet und diese ändert sich wenigstens alle hundertstel Sekunden.

Randomize;	Anweisung zur Ermittlung des Startwertes für den Zufallsgenerator
Random(x);	Funktion zum Erzeugen einer Zufallszahl im Bereich 0 <= Zahl < x

Beispiele:

Simulation eines Würfels: Randomize; wurf := Random(6)+1;   Es sind 1000 Zufallszahlen im Bereich von 0 bis 10000 zu erzeugen und in einer ListBox anzuzeigen. Randomize; for i := 0 to 999 do   ListBox1.Items.Add(IntToStr(Random(10001)));   zuf sei als Feld ganzer Zahlen deklariert und soll mit 20 Zufallszahlen im Bereich von 0 bis 100 belegt werden. Randomize; for i := 0 to 19 do   zuf[i] := Random(101);   Beachte: Randomize darf nur einmal, und zwar vor der Zählschleife aufgerufen werden, da sonst aufgrund der Geschwindigkeit des Rechners innerhalb 1/100 Sekunde immer wieder derselbe Startwert erzeugt wird, ergo auch gleiche "Zufallszahlen" entstehen.

Seitenanfang

3.3. Sequentielles Suchen

Bei der sequentiellen Suche vergleicht man den Suchschlüssel der Reihe nach mit den Schlüsseln der Feldelemente, beginnend mit dem ersten. Die Suche ist beendet, wenn man ein Element antrifft, dessen Schlüssel gleich dem Suchschlüssel ist, oder wenn man alle Elemente des Feldes verglichen hat, ohne den Suchschlüssel anzutreffen.

Bei der Suche nach dem Minimum oder Maximum eines Feldes stellt sich die Frage nach dem Suchschlüssel anders, denn man weiß ja vorher nicht, welchen Wert das Minimum bzw. Maximum hat.

Für die Suche nach dem Minimum modifiziert sich obiger Algorithmus daher wie folgt:
Man merke sich den Wert des ersten Feldelementes und vergleiche diesen mit den zweiten. Falls das zweite Element kleiner ist, merke man sich dessen Wert und vergleiche anschließend mit dem dritten usw. bis man alle Feldelemente verglichen hat.

Neben dem Wert des Minimums an sich ist meist auch noch dessen Position im Feld bzw. in der Liste von Interesse (besonders im Hinblick auf das spätere Sortieren).

Struktogramm Minimum-Suche (in einem Feld ganzer Zahlen)	Object-Pascal-Text der Minimum-Suche (in einer ListBox, Stringliste aus Zifferzeichen)
	with ListBox1 do begin   min := StrToInt(Items[0]);   pos := 0;   for i := 1 to Items.Count - 1 do     if StrToInt(Items[i]) < min then begin       min := StrToInt(Items[i]);       pos := i     end {of if} end; {of with} Edit4.Text := IntToStr(min); Edit5.Text := IntToStr(pos);

Seitenanfang

3.4. Algorithmen von Sortierverfahren

Sortieren ist nicht gleich Sortieren!

Meist sortiert man eine Datenmenge mit dem Ziel, später in dieser nach bestimmten Kriterien effektiv suchen und auswählen zu können. Denken wir z.B. an ein Telefonbuch: Eine vereinfachte Modellierung der Datenobjekte könnte wie folgt aussehen:

Offensichtlich sind für zielgerichtetes Sortieren die Sortierkriterien und deren Hierarchie entscheidend. Sortiere Telefonbuch nach:   - Anschrift.Ort     - Name.Nachname        - Name.Vorname           - Anschrift.Straße              - Anschrift.Hausnummer                 - Rufnummer Das Sortieregebnis könnte dann so aussehen: Plauen   ...   Müller, Falk   Müller, Frank   Müller, Frank   Müller, Frank   Müller, Frederike    ...   ... Birnenweg 6 Apfelbaumweg 11 Zwetschgenweg 34  Zwetschgenweg 34  Kastanienweg 41 ...   ... 314279 227495 368812 368942 734519 ...

Wenngleich auch der Sortiervorgang einfacher wäre, so würde es dem gewöhnlichen "Leser" eines Telefonbuches gar wenig nützen, hätte man dieses primär nach Rufnummern sortiert ;-)

Neben der Auswahl und Hierarchisierung der Suchkriterien bei komplexen Datenobjekten spielen auch die Sortieralgorithmen eine wesentliche Rolle. Es gibt einfach zu programmierende, die bei einer größeren Datenmenge unerträglich lange dauern und komplizierter zu programmierende, die flink sind wie die Wiesel!

Die nachfolgenden beiden Sortieralgorithmen beziehen sich auf ein eindimensionales Feld ganzer Zahlen namens zfeld mit n Elementen.

3.4.2. Sortieren durch Austauschen
Beschreibung: Beim ersten beginnend wird der Reihe nach jedes Feldelement mit all seinen Nachfolgern verglichen und sich der jeweils kleinste Nachfolger gemerkt. Ist dieser kleiner als das betreffende Feldelement, so werden beide ausgetauscht.
Struktogramm:	Delphi-Prozedur: procedure TForm1.Button6Click (Sender:TObject); {Sortieren durch Austauschen} var min, n, i, j, merke: integer; begin {Eingabe Zahlenfeld (n = Anz.der Feldelemente)} n := ListBox1.Items.Count - 1; ... {Sortiervorgang} for i := 0 to n - 1 do begin   min := zfeld[i];   merke := i;   for j := i+1 to n do     if zfeld[j] < min then begin       min := zfeld[j];       merke := j;     end {of if};   hilf := zfeld[merke];   zfeld[merke] := zfeld[i];   zfeld[i] := hilf; end; {of for} {Ausgabe Zahlenfeld} ... end;

 

Quicksort

Beschreibung: Das Feld wird über ein Trennelement aus der Feldmitte in zwei Teilfelder zerlegt. Alle Elemente, die größer sind als das Trennelement, werden rechts von diesem und die kleineren links davon abgelegt. Die entstandenen Teillisten werden ebenso behandelt bis keine weitere Zerlegung mehr möglich ist. (Rekursives Vorgehen!)

Delphi-Prozedur: Bezüglich obiger Aufgabenstellung ist die nachfolgende Prozedur "einbaufertig", sofern gleiche Komponenten und gleiche Bezeichner verwendet wurden. Zwecks späterem Effizienzvergleichs werden die Anzahl der Vergleiche und Vertauschungen mitgezählt und über Labels ausgegeben. Zur besseren Erkennbarkeit der Schachtelung der eingebauten Unterprogramme sind zusammengehörende Prozedurköpfe und -rümpfe jeweils in der gleichen Farbe dargestellt. Es scheint sich die obige Bemerkung zu bestätigen, dass schnelle Sortieralgorithmen nicht ganz unkompliziert zu programmieren sind ;-) procedure TForm1.Button8Click(Sender: TObject);   procedure quicksort(var a: feldtyp; erstes, letztes: integer);     {Sortieren mittels Quicksort}     var linker_merker, rechter_merker : integer;     procedure zerlege (var a: feldtyp; var links, rechts: integer);       var pivot: integer;       procedure tausche (var x, y: integer);         var hilf: integer;         begin           hilf := x; x := y; y := hilf;           vertausche := vertausche + 1;         end; {of vertausche}       begin {zerlege}         pivot := a[(links + rechts) DIV 2];         repeat           while a[links] < pivot do begin             links := links + 1;             vergleiche := vergleiche + 1;           end;           while a[rechts] > pivot do begin             rechts := rechts - 1;             vergleiche := vergleiche + 1;           end;           if links <= rechts then begin             tausche (a[links], a[rechts]);             links := links + 1; rechts := rechts - 1;             vergleiche := vergleiche + 1;           end;         until links > rechts;       end;{of zerlege}     begin {quicksort}       linker_merker := erstes; rechter_merker := letztes;       zerlege (a, linker_merker, rechter_merker);       if erstes < rechter_merker then         quicksort (a, erstes, rechter_merker); {Rekursiver Selbstaufruf!}       if linker_merker < letztes then         quicksort (a, linker_merker, letztes); {Rekursiver Selbstaufruf!}     end; {of quicksort}   begin {Button8Click}     vergleiche := 0;     vertausche := 0;     screen.cursor := crhourglass;     lies_zahlfeld_ein;     quicksort(z, 0, listbox1.items.count - 1);     gib_zahlfeld_aus;     screen.cursor := crdefault;     label15.caption := floattostr(vergleiche);     label16.caption := floattostr(vertausche);     edit10.text := floattostr(vergleiche + vertausche);  end;

Seitenanfang

3.5. Effizienzvergleich der Sortieralgorithmen

Sortieren durch Austauschen

Wenn man den vom Rechner zu betreibenden Aufwand beim Sortieren auf die Anzahl der durchzuführenden Vergleichsoperationen beschränkt, so verrät der Algorithmus selbst den Aufwand, der für seine Abarbeitung notwendig ist.

"Beim ersten beginnend wird der Reihe nach jedes Feldelement mit all seinen Nachfolgern verglichen ..."

Da das erste Element n-1 Nachfolger hat, das zweite n-2 Nachfolger usw. ergibt sich folgende Tabelle:

Durchläufe Vergleiche 1. n-1 2. n-2 3. n-3 ... ... n-2. 3 n-1. 2 n. (letzter) 1

Es lässt sich unschwer erkennen, dass die durchschnittliche Anzahl der Vergleiche pro Durchlauf  bei  n/2  liegt. Da aber n Durchläufe erforderlich sind, ist der Aufwand    AA(n) ~ n*n/2,  also AA(n) ~ ½ n2 und letztlich:  AA(n)~n2 Folglich liegt eine quadratische Abhängigkeit vor, d.h. es wächst der Sortieraufwand mit dem Quadrat der Feldgröße! Da nicht jeder Rechner gleich schnell arbeitet, muss für die Ermittlung des zeitlichen Aufwandes eine rechnerspezifische Zeitkonstante, nennen wir sie c, eingeführt werden: AA = ½ n2 * c

Die Zeitkonstante c ist für den eigenen Computer bestimmbar, indem man für eine geeignete Feldgröße die Sortierzeit mit der Stoppuhr (oder programmiertechnisch) ermittelt und dann obige Formel benutzt.

Beachte:

Die Zeiten zum Einlesen bzw. zur Ausgabe der Feldelemente über die ListBox dürfen natürlich nicht der Sortierzeit zugeschlagen werden. Beim zum Download angebotenen Programm wird daher die eigentliche Sortierzeit über ein rotes Einfärben des zur Aktivitätsanzeige genutzten Textfeldes verdeutlicht.

 

Quicksort

Die Herleitung des Sortieraufwandes über den Algorithmus dieses Verfahrens würde den Rahmen der vorliegenden Seite sprengen. Daher sei an dieser Stelle nur die Formel angegeben, die bei guter Näherung die Abhängigkeit A_Q(n) beschreibt:

AQ(n) ~ n * lg(n)	bzw. mit Zeitkonstante:
AQ(n) = c * n * lg(n)

Der "Traum" einer linearen Abhängigkeit der Sortierzeit von der Feldgröße geht also auch hier nicht in Erfüllung (genauso wenig wie der Traum vom Perpetuum mobile!)
Dennoch zeigt sich die haushohe Überlegenheit dieses innovativen Sortierverfahrens gegenüber den einfacheren mit quadratischer Abhängigkeit!

Beispiel:

Elemente	Sortieren durch Austauschen	Quicksort
100	AA(100)=1002/2*c AA(100)=5000c	AQ(100)=100*lg(100)*c = 100*2*c AQ(100)=200c
10000	AA(10000)=100002/2*c AA(10000)=50000000c AA(10000)=5*107c	AQ(10000)=10000*lg(10000)*c = 10000*4*c AQ(10000)=40000c AQ(10000)=4*104c

Diplomarbeiten zum Runterladen: