Matura aus informatik
Spezialgebiet aus Informatik
Sortieralgorithmen
Ulrich BREUNIG, 8A Wien, am 16. März 2000
Inhaltsverzeichnis
Einführung 3
Allgemeiner Programmcode 3
Selection Sort (Sortiern durch Auswahl) 4
Insertion Sort (Sortieren durch Einfügen) 5
Bubble Sort (Sortieren durch Austauschen) 7
Merge Sort (Sortieren durch Mischen) 8
Radix Exchange Sort (Sortieren durch rekursiven Bitvergleich) 10
Quick Sort (Sortieren durch Zerlegen) 12
Fallstricke und Fußangeln 14
Sortieren auf Datenträger 14
Nutzung des Hauptspeichers 14
Optimierungen 14
Kurzübersicht 15
Algorithmen mit Aufwand O(n2) mit unsortierten Daten 15
Algorithmen mit Aufwand O(n ln(n)) mit unsortierten Daten 15
Einführung
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.
Allgemeiner Programmcode
Die folgenden Programmzeilen werden für alle behandelten Sortieralgorithmen verwendet.
Definitionen und Deklarationenconst HighMax = 999999; // Maximale Daten-Arraygröße
type TArray = array [0..HighMax] of integer; // Typ des Daten-Arrays
Hilfs-Procedureprocedure Swap (var i, j: integer);
// Vertauscht die beiden Zahlen i und j
var h: integer;
begin
h:= i;
i:= j;
j:= h;
end;
Selection Sort (Sortiern durch Auswahl)
Beschreibung
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.
Programmcodeprocedure 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
Aufwandsabschätzung
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)).
Sortierdauer
Insertion Sort (Sortieren durch Einfügen)
Beschreibung
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.
Programmcodeprocedure 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
Aufwandsabschätzung
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 .
Sortierdauer
Bubble Sort (Sortieren durch Austauschen)
Beschreibung
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.
Programmcodeprocedure 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
Aufwandsabschätzung
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).
Sortierdauer
Merge Sort (Sortieren durch Mischen)
Beschreibung
Das Verfahren arbeitet rekursiv nach dem Divide & Conquer – 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.
Programmcodeprocedure 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
Aufwandsabschätzung
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.
Sortierdauer
Bemerkung:
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.
Radix Exchange Sort (Sortieren durch rekursiven Bitvergleich)
Beschreibung
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.
Programmcodeprocedure 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
Aufwandsabschätzung
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) » 17.
Daraus folgt der Aufwand , wobei N der Wertebereich ist. Da im Allgemeinen der Wertebereich wesentlich größer ist als die Anzahl der Elemente Þ .
worst-case-Aufwand:
w.o.
Sortierdauer
Quick Sort (Sortieren durch Zerlegen)
Beschreibung
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.
Programmcodeprocedure 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
Aufwandsabschätzung
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 .
Sortierdauer
Fallstricke und Fußangeln
Sortieren auf Datenträger
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.
Nutzung des Hauptspeichers
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.
Optimierungen
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.
Beispiele
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.
| Anmerkungen: |
| impressum | datenschutz
© Copyright Artikelpedia.com
