Sortieralgorithmen
Das Sortieren von Daten ist ein klassisches Problem der Informatik. Die Verwaltung von Datenbanken jedweder Ausprägung erfordert häufig den Einsatz eines effizienten Sortieralgorithmus. Das Wesentliche an einem Sortierverfahren ist natürlich seine Geschwindigkeit. Darum wird jeder der vorgestellten Algorithmen bezüglich seines Aufwands abgeschätzt werden. Die Aufwandsabschätzung ist eher abstrakt und nicht von konkreten Daten oder technischen Systemen abhängig. Darum darf man in der Realität folgende Punkte nicht aus den Augen verlieren:
Welche Daten sollen sortiert werden? (Integer-Zahlen, Gleitkomma-Zahlen, Zeichenketten, )
Wie groß ist die Anzahl der zu sortierenden Datensätze?
Nach welchen Kriterien soll sortiert werden (z.B. aufsteigend, absteigend, Reihenfolge der Buchstaben eines Zeichensatzes, )? => Eine Vergleichsfunktion wird benötigt.
Haben die Daten bereits eine (teilweise) Ordnung (zum Beispiel sind sie bis auf Ausnahmen schon sortiert, )?
Auf welchen Medien soll sortiert werden (Hauptspeicher, Medien mit wahlfreiem Zugriff (Festplatten) oder sequentiellen Zugriff (Bänder))?
Wieviel Speicher steht zur Verfügung?
Sind doppelte Datensätze erlaubt (z.B. zweimal "Fritz Maier", )?
In den nachfolgenden Kapiteln sollen nun Sortierverfahren für den Hauptspeicher betrachtet werden.
Die folgenden Programmzeilen werden für alle behandelten Sortieralgorithmen verwendet.
const HighMax = 999999; // Maximale Daten-Arraygröße
type TArray = array [0..HighMax] of integer; // Typ des Daten-Arrays
procedure Swap (var i, j: integer);
// Vertauscht die beiden Zahlen i und j
var h: integer;
begin
h:= i;
i:= j;
j:= h;
end;
Aus den vorhandenen Daten wird der kleinste Datensatz herausgesucht und mit dem ersten Datensatz vertauscht.
Dieses Verfahren wird nun für die übriggebliebenen, noch unsortierten Daten ebenfalls angewandt.
procedure SelectionSort ( var f : TArray; HighIndex : integer ) : string;
var i, j, min : integer;
begin
for i := 0 to HighIndex-1 // äußere Schleife
do begin
min := i;
for j := i+1 to HighIndex do if f[j] < f[min] then min := j; // innere Schleife
Swap (f[i], f[min]);
end;
end; // SelectionSort
mittlerer-Aufwand:
Die äußere Schleife wird n-1 mal durchlaufen.
Die innere Schleife wird im Durchschnitt (n-1)/2 mal durchlaufen.
Daraus folgt der Aufwand 
.
worst-case-Aufwand:
Der maximale Aufwand beträgt ebenfalls O(n2).
Sortierverfahren mit quadratischen Aufwand sind schlecht und eignen sich nur für kleine Datenmengen. Ihre Rechtfertigung liegt einzig und allein in der einfachen Implementierung. Wie wir später sehen werden, gibt es wesentlich effizientere Sortierverfahren mit einem Aufwand von O(n ln(n)).
Die Elemente werden der Reihe nach in eine bereits sortierte Folge eingetragen.
Dazu wird in der bereits sortierten Folge die richtige Stelle zum Einfügen von rechts her gesucht und gleichzeitig die bereits eingetragenen Elemente um eins nach rechts verschoben.
Das neue Element wird dann an der auf diese Weise freigewordenen Position eingefügt.
procedure InsertionSort ( var f : TArray; HighIndex : integer ) : string;
var i, j, v : integer;
begin
for i := 1 to HighIndex // äußere Schleife
do begin
v := f[i];
j := i;
while (j>0) and (f[j-1] > v) // innere Schleife (zum Einfügen)
do begin
f[j] := f[j-1];
dec (j)
end;
f[j] := v
end;
end; // InsertionSort
mittlerer-Aufwand:
Die äußere Schleife wird n-1 mal durchlaufen.
Die innere Schleife wird ½ * ½ (n-1) durchlaufen. (Im Mittel erwarten wir, daß das neue Element in die Mitte des soriterten Bereichs gehört.)
Daraus folgt der Aufwand 
.
worst-case-Aufwand:
Die äußere Schleife wird n-1 mal durchlaufen.
Die innere Schleife wird ½ (n-1) durchlaufen.
Daraus folgt der Aufwand 
.
best-case-Aufwand:
Die äußere Schleife wird n-1 mal durchlaufen.
Die innere Schleife wird 1 mal durchlaufen, da jedes neue Element schon am richtigen Platz steht, d.h. das Array war schon aufsteigend sortiert.
Daraus folgt der Aufwand 
.
Die Daten werden in einer doppelten Schleife abgearbeitet.
Die innere Schleife umspannt jeweils den gesamten unsortierten Bereich: Dieser wird iterativ durchgearbeitet. Wenn ein Element größer ist als sein rechter Nachbar, so werden sie miteinander vertauscht.
Nach jedem äußeren Schleifendurchlauf wurde der sortierte Bereich am Ende der Daten um mindestens 1 erhöht.
procedure BubbleSort ( var f : TArray; HighIndex : integer ) : string;
var i, j : integer;
begin
for i := HighIndex downto 1 // äußere Schleife
do for j := 0 to i
do if f[j] > f[j+1] then swap (f[j], f[j+1]); // innere Schleife
end; // BubbleSort
mittlerer-Aufwand:
Die äußere Schleife wird n-1 mal durchlaufen.
Die innere Schleife wird im Durchschnitt (n-1)/2 mal durchlaufen.
Daraus folgt der Aufwand .
worst-case-Aufwand:
Der maximale Aufwand beträgt ebenfalls O(n2), da beide Schleifen auch im schlechtesten Fall genauso oft durchlaufen werden. Der Unterschied ist nur die Anzahl der benötigten Tauschvorgänge (im besten Fall ist gar keiner nötig).
Das Verfahren arbeitet rekursiv nach dem Divide & Conquer[1] - Prinzip.
Die Folge wird rekursiv bis zur trivilaen Teilfolge der Länge 1 zerteilt (Divide).
Diese Teilfolgen werden jeweils durch Merging vereint, die vereinten wiederum. etc. bis zur sortierten Gesamfolge (Conquer).
Es wird ein zusätzliches Hilfsfeld Ziel von der gleichen Größe wie die zu sortierende Gesamtfolge benötigt.
procedure MergeSort ( var f : TArray; HighIndex : integer ) : string;
var Ziel : TArray; // Hilfsfeld zum Einsortieren für die Procedure Merge
procedure Merge ( links, mitte, rechts : integer );
var h, i, j, k : integer;
begin
i := links; // Index des linken Teilfeldes
j := mitte + 1; // Index des rechten Teilfeldes
k := links; // Index des (sortierten) Hilfsfeldes
repeat
if f[i] < f[j]
then begin ziel[k] := f[i]; inc (i); end
else begin ziel[k] := f[j]; inc (j); end;
inc (k);
until (i > mitte) or (j > rechts);
if i > mitte
then for h := j to rechts do ziel [k+h-j] := f[h]
else for h := i to mitte do ziel [k+h-i] := f[h];
for h := links to rechts do f[h] := Ziel [h]; // zurückkopieren ins Datenfeld
end; // subproc Merge
procedure rMergeSort (links, rechts : integer);
// rekursiver Teil des MergeSorts
var mitte : integer;
begin
if links < rechts
then begin
mitte := (links + rechts) div 2;
rMergeSort (links , mitte ); // sortieren des linken Teils
rMergeSort (mitte+1 , rechts); // sortieren des rechten Teils
Merge (links, mitte, rechts); // zusammenmischen der beiden Teile
end;
end; // SubProc MergeSort
begin // MergeSort
rMergeSort (0, HighIndex);
end; // MergeSort
Aufwand:
Die Datenmenge wird in n Teile zerlegt. Dazu sind insgesamt ld(n) Rekursionsschritte notwendig.
Im Durchschnitt werden n/2 Elemente miteinander gemischt.
Daraus folgt der Aufwand 
.
worst-case-Aufwand:
w.o.
Die etwas seltsame Krümmung der Graphen entsteht dadurch, daß die gemessene Zeit sehr klein ist (nicht einmal eine Sekunde) und die Datenmenge groß. Dadurch ist jede Betriebssystemaktivität wie z.B. Seitenauslagerungen zu sehen.
Die Daten werden mit einem rekursiven Verfahren (Divide & Conquer) anhand ihrer Bitstruktur sortiert.
Daten mit gesetztem n-ten Bit kommen in die rechte Hälfte, die anderen in die linke; für beide Hälften wird das Verfahren rekursiv aufgerufen.
procedure RadixExchangeSort ( var f : TArray; HighIndex : integer ) : string;
function Bit ( z, b : integer ) : integer;
// liefert das Bit mit der Nummer b einer positiven Integerzahl
begin
result := ((z shr b) and 1) // Rausschneiden des Bits b aus der Zahl z
end;
procedure rRadixExchangeSort ( links, rechts, b : integer);
// rekursiver Teil des RadixExchangeSorts
var i, j : integer;
begin
if (links < rechts) and (b >= 0)
then begin
i := links;
j := rechts;
repeat
while (Bit (f[i], b) = 0) and (i < j) do inc (i);
while (Bit (f[j], b) = 1) and (i < j) do dec (j);
swap (f[i], f[j]);
until i = j;
// Korrigiere Spezialfall, daß alle Elemente nur in d. rechten Hälfte waren:
if Bit (f[rechts], b) = 0 then inc (j);
rRadixExchangeSort (links, j-1 , b-1);
rRadixExchangeSort (j, rechts , b-1);
end;
end; // rRadixExchangeSorts
begin // RadixExchangeSorts
rRadixExchangeSort (0, HighIndex, 30);
end; // RadixExchangeSorts
Aufwand:
In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n-Elemente.
Die Rekursionstiefe hängt vom Wertebereich (signifikanten Bits) des Schlüssels ab, bei Integerzahlen im Bereich 1 - 100.000 beträgt die Rekusionstiefe ld (100.000)
Daraus folgt der Aufwand 
, wobei N der Wertebereich ist. Da im Allgemeinen der
Wertebereich wesentlich größer ist als die Anzahl der Elemente T 
.
worst-case-Aufwand:
w.o.
Das Verfahren arbeitet nach dem Divide & Conquer-Prinzip.
Aus einer zu sortierenden Teilfolge wird ein Element ausgewählt.
Die Folge wird so umsortiert, daß das ausgewählte Element an seine insgesamt (bezogen auf den Sortiervorgang der vollständigen Datenfolge) richtige endgültige Position zu liegen kommt.
Nach dem Umordnen dürfen links vom ausgewählten Element nur mehr kleinere Elemente stehen und rechts nur mehr größere.
Dann wird für die Folgen links und rechts vom ausgewählten Element das Verfahren rekursiv aufgerufen.
Das korrekte Umordnen wird dadurch erreicht, daß von links her Elemente gesucht werden, die in die rechte Hälfte gehören, und von rechts her solche, die in die linke Hälfte gehören. Dann werden diese falsch plazierten Elemente vertauscht. Das Umordnen endet, wenn die beiden Suchvorgänge an der endgültigen Position des ausgewählten Elements zusammenstoßen.
procedure QuickSort ( var f : TArray; HighIndex : integer ) : string;
procedure rQuickSort ( links, rechts : integer);
// rekursiver Teil des QuickSorts
// Als Trennelement wird das jeweils mittlere Element der Teilfolge ausgewählt.
var i, j, x : integer;
begin
if links < rechts
then begin
i := links;
j := rechts;
x := f[(i+j) div 2]; // Wert des Trennelements
repeat
while f[i] < x do inc(i);
while f[j] > x do dec(j);
if i < j then swap (f[i], f[j]);
until i >= j;
rQuickSort (links, j-1 );
rQuickSort (j+1 , rechts);
end;
end; // rQuicksort
begin // QuickSort
rQuickSort (0, HighIndex);
end; // QuickSort
Aufwand:
In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n-Elemente.
Die Rekursionstiefe hängt davon ab welches Element als Trennelement gewählt wurde. Im besten Fall wird immer genau das tatsächlich mittlere gewählt, dann ist die Rekursionstiege ld (n). Normalerweise wird das gewählte Trennelement nicht genau das mittlere sein, sodaß sich die Rekursionstiefe etwas verschlechtert: ~ 1,4 ld (n).
Daraus folgt der Aufwand 
.
worst-case-Aufwand:
Wenn zufällig immer das kleinste oder das
größte Element als Trennelement auswählt wird, beträgt die Rekursionstiefe n/2
und somit der Aufwand 
.
Solange alle Daten im Hauptspeicher Platz haben, stimmen die obigen Aufwandsabschätzungen. In vielen Fällen sind die Datenmengen aber so groß, daß sie nur in großen Dateien auf Datenträgern Platz finden.
Meist wird nach einem Schlüssel (Kundennummer, Namen, ) sortiert und die übrigen Daten (Adresse, ) werden mitkopiert. Die Aufgabe vereinfacht sich stark, wenn es möglich wird, den Schlüssel sowie den Verweis auf den dazugehörigen Datensatz (Record-Nummer) im Speicher unterzubringen.
In jedem Fall erfordert der langsame Zugriff auf Dateien ganz andere Lösungsstrategien für Sortierverfahren.
Um auch größere Datenmengen effizient sortieren zu können, muß man den zur Verfügung stehenden Speicher effizient nutzen. Man muß also versuchen, einen möglichst großen Teil des Hauptspeichers für das Programm zu reservieren, um möglichst wenig auf den sehr viel langsameren (Faktor 1000 und mehr) Sekundärspeicher (Festplatte, ) zurückgreifen zu müssen.
Bei der Aufwandsabschätzung zählt man die Größenordnung der geleisteten Arbeit. Allerdings kann der Einsatz gezielter Optimierungen (natürlich unter Verwendung von Kenntnissen über die interne Verarbeitung durch den Compiler und Hardware) die Abschätzung völlig auf den Kopf stellen.
Es muß daher immer sorgfältig betrachtet werden, ob nicht weitergehende Annahmen (zum Beispiel in Hinblick auf Struktur und Umfang der zu erwarteten Datenmenge) im Einzelfall gezielte Optimierungen erlauben.
MergeSort: Für die Subprocedure Merge wird das Hilfsarray Ziel benötigt. Deklariert man das Hilfsarray als lokale Variable innerhalb von Merge anstatt global zu Merge, benötigt der Algorithmus die zehnfache Zeit, da nun bei jedem Aufruf (also insgesamt n*ld(n)-mal) die Variable Ziel (400 KB!) neu am Stack angelegt und anschließend wieder vernichtet werden muß.
QuickSort: Wird statt der globalen Procedure swap das Vertauschen von zwei Variablen schon innerhalb des Sortieralgorithmus implementiert, so verbessert sich die Performance um ca. 30%, da nun die Procedureaufrufe für swap entfallen.
usw
Haupt | Fügen Sie Referat | Kontakt | Impressum | Nutzungsbedingungen
