SUCHE MIT Google
Web virtualuniversity.ch
HOME DIDAKTIK ECDL ELEKTRONIK GUIDES HR MANAGEMENT MATHEMATIK SOFTWARE TELEKOM
DIENSTE
Anmeldung
Newsletter abonnieren
Sag's einem Freund!
VirtualUniversity als Startseite
Zu den Favoriten hinzufügen
Feedback Formular
e-Learning für Lehrer
Spenden
Autoren login
KURSE SUCHEN
Kurse veröffentlichen

Suche nach Datum:

Suche mit Schlüsselwort:

Suche nach Land:

Suche nach Kategorie:
PARTNER
ausbildung24.ch - Ausbildungsportal, Seminare, Kursen... 

 
HTMLopen.de - Alles was ein Webmaster braucht

 
PCopen.de - PC LAN Netze und Netzwerke - alles was ein IT Profi und Systemtechnicker braucht

SOFTWARE

PÜ 13: Felder, Such- und Sortierverfahren

Downloads:  sortiere.com (Zip)
feldsort.exe

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
feldsrt1.jpg (25260 Byte)
  1. Ü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
     
  2. 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
feldsrt3.jpg (20370 Byte)
  1. 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
     
  2. 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
feldsrt2.jpg (22666 Byte)
  1. 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
      
  2. 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
      
  3. 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.)!
      
  4. 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
pfeil_lu.gif (1095 Byte)   pfeil_ru.gif (1096 Byte)
Datentyp Feld (ARRAY)

für Operationen mit den Daten
z.B. Suchen, Sortieren

Daten-
pfeil_lr.gif (1058 Byte)
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

listboxp.jpg (7309 Byte) 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:
  1. Anzeige des Index des markierten Listenelementes über Label1:
    Label1.Caption := IntToStr(ListBox1.ItemIndex);
     
  2. 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:
  1. Simulation eines Würfels:
    Randomize;
    wurf := Random(6)+1;
     
  2. 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)));
     
  3. 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)
strksuch.jpg (20030 Byte) 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:

telefonb.jpg (7463 Byte) 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 AQ(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 UND BÜCHER

Diplomarbeiten zum Runterladen:

Suche im Katalog:
Architektur / Raumplanung
Betriebswirtschaft - Funktional
Erziehungswissenschaften
Geowissenschaften
Geschichtswissenschaften
Informatik
Kulturwissenschaften
Medien- und Kommunikationswissenschaften
Medizin
Psychologie
Physik
Rechtswissenschaft
Soziale Arbeit
Sozialwissenschaften


JOBS
HOME | E-LEARNING | SITEMAP | LOGIN AUTOREN | SUPPORT | FAQ | KONTAKT | IMPRESSUM
Virtual University in: Italiano - Français - English - Español
VirtualUniversity, WEB-SET Interactive GmbH, www.web-set.com, 6301 Zug

Partner:   Seminare7.de - PCopen.de - HTMLopen.de - WEB-SET.com - YesMMS.com - Ausbildung24.ch - Manager24.ch - Job und Karriere