Sortieralgorithmen

Zum Sortieren von Daten (hier: Zahlen) gibt es verschiedene Verfahren, die je nach Situation schneller oder langsamer sind. Drei davon werden hier vorgestellt.

Sortieren durch Einfügen

Das Feld

2 8 7 1 7 4

soll aufsteigend sortiert werden. Man beginnt mit der zweiten Stelle und vergleicht diese mit der ersten Stelle. Da diese beiden Stellen sortiert sind (2 < 8), geht man zur dritten Stelle. Da die 7 zwischen 2 und 8 liegt, wird sie einer Hilfsvariablen zugeteilt, damit die Stelle mit Index 3 frei wird.

2 8   1 7 4

Alle Elemente, die größer als 7 sind (d.h. die 8) rücken nun um eine Stelle nach rechts. Ist man damit fertig, rückt an die freie Stelle die 7.

2 7 8 1 7 4


Analog fährt man mit der vierten, fünften, ... Stelle fort. 

2 7 8   7 4
1 2 7 8 7 4
1 2 7 8   4
1 2 7 7 8 4
1 2 7 7 8  
1 2 4 7 7 8

Bei diesem Verfahren ist das Feld immer in einen sortierten, linken und einen unsortierten, rechten Abschnitt aufgeteilt.

Rahmenprogramm:


Die Prozedur EinSort hat dabei folgende Gestalt:

Sortieren durch direktes Auswählen:

Vom ersten bis zum vorletzten Element wird der kleinste Wert aus dem noch nicht sortierten Teil direkt ausgewählt und an den sortierten Teil angefügt durch:
1. Suchen des kleinsten Wertes im Rest
2. Speichern diese Wertes in einer Hilfsvariablen
3. Verschieben aller Werte zwischen diesem und der Trennstelle nach oben
4. Wiedereinfügen des Wertes an der Trennstelle


Die Prozedur muss wieder an die gleiche Stelle in das Rahmenprogramm eingetragen werden.

BubbleSort

Das Feld wird von unten nach oben abgesucht. Durch Vertauschung von falsch stehenden Elementen (großer vor kleinem Wert) wandern die großen Werte wie Blasen im Feld nach oben.
Wenn keine Vertauschung mehr stattgefunden hat, ist das Feld sortiert.

Musterlösung

Vergleich von Sortierverfahren

Die Sortierverfahren sollen nun getestet werden. Die Musterlösung besteht aus einem fertigen Modul, das alle drei behandelten Algorithmen enthält.

Aufgaben

1. Mache dich mit dem Ablauf und dem Quelltext des Programms vertraut!

2. Die Feldgröße soll bis zur Obergrenze 16375 bei sortierten und unsortierten Feldern untersucht werden. Eine Eingabe der Feldwerte per Hand wäre müßig. Die folgenden Prozeduren (mit und ohne den kursiven Teil) erzeugen ein sortiertes und ein "unsortiertes" (absteigend sortiertes) Feld. Sie finden sich bereits im Quelltext der Musterlösung.

PROCEDURE FeldUnSortiert (VAR feld: DatenFeld);
VAR 
     i:INTEGER;
BEGIN
     FOR i:=untergrenze TO obergrenze DO
          feld [i]:=i; / feld [i]:=obergrenze-i; (*alternativ!*)
          Display. WriteInt (feld[i], 3);
     END;
END FeldSortiert;

3. Ermittle die Zahl der Arbeitsschritte für verschiedene Obergrenzen und erstelle eine Tabelle nach folgender Form in deinem Heft:

Ursprünglich sortiertes Feld EinSort AuswahlSort BubbleSort
1      
100      
1000      
16000      

Gehe ebenso für das unsortierte Feld vor!

6. Zeichne einen Graphen für EinSort, in dem du die Arbeitsschritte gegen die Feldgröße aufträgst (Achsen sinnvoll wählen!). Welche Art von Kurve ergibt sich?

Zurück zur Übersicht über weitere Themen