Sortieren
(Die italic gesetzten Passagen können von denen überlesen werden, denen
Überlegungen ein Grauen sind, die nach Mathematik riechen)
Wir stellen hier hier einige Sortierverfahren vor, an denen einige Techniken der Algorithmik studiert werden können. Sortieren setzt voraus, daß die zu sortierenden Elemente vergleichbar sind, d.h. daß sie aus einer Menge stammen, der eine (lineare) Ordnung zugrunde liegt. Dies ist z.B. für die ganzen Zahlen (Integer) der Fall, die wir daher als Repräsentanten sortierbarer Elemente nehmen. Grundlegend für die hier vorgestellten Algorithmen ist, daß wir über die Elemente nichts weiter wissen, als daß sie aus einer Ordnung stammen und daß wir entscheiden können, welches Element im Sinne dieser Ordnung größer oder kleiner ist.
Es gibt auch Sortieralgorithmen, die Eigenschaften von Elementen nutzen, die wir hier nicht kennen. So kann z.B. die Menge der Worte über einem Alphabet linear ordnen, sodaß man sagen kann welches von zwei Worten größer ist, aber man weiß von einem Wort darüber hinaus, wie es aufgebaut ist. Daraus kann man Nutzen ziehen, wie es etwa BucketSort tut. So kommt man zu schnelleren Verfahren, als es mit den Sortieren nur durch Vergleich möglich ist. Man kann beweisen, daß kein Sortierverfahren nur durch Vergleich mit weniger als n*log(n) Vergleichen auskommt. Setzt man allerdings andere Techniken ein, so kann man den Aufwand unter diese Zeitschranke drücken.
Wir stellen zunächst zwei "dumme" Sortierverfahren vor (BubbleSort
und MinSort), die im schlimmsten Fall (worst case) quadratischen Aufwand
benötigen (Bei n Elementen können bis zu n2 Vergleiche nötig
sein.) Danach kommen intelligentere Verfahren, die alle in irgendeinem Sinn
besser sind, die uns aber vor allem verschiedene Techniken demonstrieren, die
auf dem Gebiet der "Effizienten Algorithmen" Bedeutung gewonnen
haben.
Sortieren durch Aufsteigen: BubbleSort
Idee:
Man stelle sich den Array aus Integern vor als eine aufrecht gestellte
Wassersäule, in der die Integer wie Luftblasen schweben. Die großen Luftblasen
steigen auf durch die kleineren hindurch und werden erst durch noch größere
aufgehalten. Nach einiger Zeit werden sich die Luftblasen von selbst der Größer
nach geordnet haben: die kleinen unten, die großen oben.
Beispiel:
Eine Säule von 4 Integern. In drei Durchgängen wandert die 4, die
3, die schießlich die 2 an ihren Platz.
1
4 4 4
2
1 3 3
3
2 1 2
4
3 2 1
Beispiel:
Eine Säule von 6 Integern wird 6-mal durchlaufen, wobei jede Blase soweit aufsteigt,
bis sie unter einer größeren hängen bleibt. Jeder Durchgang benötigt 5
Vergleiche, 6 Durchgänge müssen wir machen. Im letzten Durchgang passiert zwar
nichts mehr, aber er ist nötig, um sicherzustellen, daß wir fertig sind. Denn
das Abbruchkriterium ist gerade, daß in einem Durchgang kein Wandern (Tauschen)
mehr stattfindet. Es sind also im schlimmsten Fall 5*6 = 30 Vergleiche nötig.
Der muß aber nicht eintreten, denn wenn die Folge schon in unserem Sinne
sortiert ist, so genügt ein einziger Durchgang, also 5 Vergleiche, um
festzustellen, daß wir fertig sind. Das ist der günstigste Fall (best case).
1
6 6 6 6
6
6
1 5 5 5
5
2
5 1 4 4
4
5
2 4 1 3
3
3
4 2 3 1
2
4
3 3 2 2
1
Aufwand:
Auf Grund der obigen Überlegungen benötigen wir, um n Elemente zu sortieren,
höchstens n Durchgänge mit je n-1 Vergleichen, das sind insgesamt n(n-1)
= n2 - n Vergleiche.
Programm ohne Prozedur:
program bubsort_1;
const n=?;
type arr=array[1..n] of integer;
var A:arr; temp,i:integer; nochmal:boolean;
begin
for i:=1 to c do read(A[i]);
repeat
nochmal:=false;
for i:=1 to
n-1 do
if A[i]>A[i+1] then begin
temp:= A[i]; A[i]:=A[i+1]; A[i+1]:=temp;
nochmal:=true;
end;
until nochmal=false;
end.
Programm mit Funktion
program bubsort_2;
const n=?;
type arr=array[1..n] of integer;
var a:arr; i:integer;
procedure tausch(i,j:integer);
var temp: integer;
begin temp:= A[i]; A[i]:=A[j]; A[j]:=temp end;
function blubber: boolean;
var i:integer;
begin
blubber:=false;
for i:=1 to n-1 do
if A[i]>A[i+1]
then begin tausch(i,i+1); blubber:=true end;
end;
begin
for i:=1 to n do read(A[i]); readln;
while blubber do
for i:=1 to
n do write(A[i]:5)
end.
Sortieren durch Minimumssuche: MinSort
Idee:
Wir lassen einen Positionszeiger durch den Array wandern und setzen an die
aktuelle Position jeweils das kleinste Element des Rest-Arrays rechts von
dieser Postition. Um dieses kleineste Element zu finden, wandern wir mit einem
zweiten Zeiger von der aktuellen Position ab bis zum Ende des Arrays und merken
uns das jeweils kleinste bisher gefundene Element.
Beispiel:
6
1 5 2 4
3 5
Vergleiche
1 6 5
2 4 3
4 Vergleiche
1 2 5
6 4 3
3 Vergleiche
1 2 3 6
4 5
2 Vergleiche
1 2 3
4 6 5
1 Vergleich
1 2 3
4 5 6
0 Vergleiche
_________________________________________________________
15 Vergleiche
Aufwand:
Offenbar müssen wir bei n Elementen (n-1)-mal das Minimum suchen. Beim ersten Mal kostet uns dies n-1 Verlgeiche, beim 2. Mal n-2, beim i-ten Mal n-i Vergleiche. D.h. die Zahl der Vergleiche ist die Summe der Zahlen von 1 bis n-1, das ist gerade (n2 - n)/2. Wir sehen, der Aufwand ist etwas kleiner als der Aufwand des BubbleSort - etwa die Hälfte, dafür ist er aber auch immer so hoch, denn selbst, wenn die Folge schon fertig sortiert vorliegt, würde unser Verfahren dies nicht feststellen, bis es alle Vergleiche durchgeführt hat.
Programm:
program minsort;
const n=?;
type arr=array[1..n] of integer;
var A: arr; i,j: integer;
procedure suchmin(pos:integer; var erg:integer);
var j,min: integer;
begin
min:=A[pos]; erg:=pos;
for j:=pos to n do
if A[j]< min
then begin min:=A[j]; erg:=j end;
end;
procedure tausch(i,j:integer);
var temp: integer;
begin temp:= A[i]; A[i]:=A[j]; A[j]:=temp end;
begin
for i:=1 to n do read(A[i])
for i:=1 to n-1 do begin suchmin(i,j);
tausch(i,j) end;
end.
Sortieren durch Mischen: Mergesort
Idee:
Dies ist nun eines der intelligenten Verfahren. Es basiert auf dem "Divide-and-Conquer"-Prinzip: man zerlegt das Original-Problem in zwei Probleme halber Größe, löst die beiden Teilprobleme und setzt dann aus den beiden Lösungen die Lösung des Originalproblems zusammen. Beim Lösen der Teilprobleme geht man genauso vor, sodaß man ein rekursives Verfahren erhält.
Der Aufwand bei einem solchen Verfahren läßt sich besonders
elegant durch eine Rekursionsgleichung beschreiben: Hat das Problem die Größe
n und ist n eine Zweierpotenz und läßt sich unser Problem
in der Größe immer genau halbieren, so ist der worst case Aufwand
unseres Problems beschreibbar durch T(n) = a falls n = 1 und T(n) =
2T(n/2) + p(n) sonst. Dabei haben wir angenommen, daß die Lösung
des Problems der Größe 1 den Aufwand a hat und daß das Zusammensetzen
der Originallösung der Größe n aus den beiden Lösungen
den Aufwand p(n) erfordert, wobei p eine arithmetische Funktion sei. Die kleinste
Lösung dieser Gleichung ist
T(n) = 2T(n/2) + p(n)
= 2( 2T(n/4) + p(n/2)
) + p(n) = 4T(n/4) + p(n) + 2p(n/2)
=
.........................
= 2kT(n/2k
) + Sumi=0,..,k-1 (2ip(n/2i))
=
.........................
= a n + Sumi=0,..,logn-1
(2ip(n/2i))
Beim MergeSort teilt man den Array von n Elementen in 2 Teilarrays von n/2 Elementen, sortiert diese und mischt nun die Elemente der sortierten Teilarrays so ineinander, daß die Elemente sortiert bleiben. Dies geschieht, indem man die jeweils ersten Elemente der beiden Teilarrays vergleicht, das kleinere der beiden löscht und in den großen Array schreibt. Dies wiederholt man, bis einer der Teilarrays leer ist. Dann kann man den Rest des anderen (sortierten) Teilarrays einfach in den großen Array abschreiben. Man sieht, daß der Aufwand beim Zusammensetzen der Teillösungen bedeutsam ist: er erfordert bis zu n-1 Vergleiche, wenn der resultierende Array die Länge n hat.
Im Fall des MergeSort sähe unsere Rekursionsgleichung also wie folgt aus:
T(n) = 0 falls n=1 und T(n) = 2T(n/2)
+(n-1) sonst. Damit bekommen wir:
T(n) = 2T(n/2) +(n-1) = ........ =
= 2kT(n/2k
) + Sumi=0,..,k-1 (2i(n/2i-1) ) wobei k
= log n
= 0 n + Sumi=0,..,k-1
(n -2i)
= n log n
- (2log n -1)
= n(log
n - 1) + 1
Beispiel:
Wir beginnen mit einem Array der Größe 16. Der wird halbiert in zwei der Größe 8, diese wieder in 4 der Größe 4 und diese in 8 der Größe 2. Diese kleinen Arrays sortieren wir, und nun mergen wir nur noch die sortierten Arrays zu neuen sortierten Arrays doppelter Größe und diese wieder zu sortierten Arrays doppelter Größe usw, bis wir wieder einen Array der Größe 16 haben.
16
teile
8
8
teile
4
4
4
4 teile
2 2
2 2 2 2
2 2 sortiere: 8 = 8*(2-1) Vergleiche
2 2
2 2 2 2
2 2 merge: 4*3 = 4(4-1)
Vergleiche
4
4
4
4 merge: 2*7 = 2(8-1)
Vergleiche
8
8
merge: 15 = 1(16-1) Vergleiche
16
_________________________________________________________________
Insgesamt
49 = 3*16 +1 Vergleiche
Aufwand:
Man erkennt die Verallgemeinerung: die Zahl der Vergleiche bei n Elementen ist offenbar ( sei k = log n):
Sumi=0,..,k-1 ( 2i
(2k-i - 1) ) = Sumi=0,..,k-1 ( 2k
- 2i ) = Sumi=0,..,k-1 ( 2k
) - Sumi=0,..,k-1 ( 2i )
= k 2k - ( 2k - 1) = n(log n -1) + 1
Um sich klar zu machen, wie groß der Fortschritt von n2 zu n*log n ist betrachten wir die Zahl n = 230 ,was etwa ein Milliarde ist, dann ist n2 = 260 , also etwa eine Milliarde Milliarden (wir nennen das im Deutschen eine Trillion), aber n* log n = 30*230 , also nur etwa 30 Milliarden. Der Unterschied zwischen 30 und einer Milliarde wird jedem auffallen. Einer, der nur 30 DM besitzt, wird glauben, daß er nichts besitzt, wenn er mit einem Milliardär spricht. Entsprechend groß ist der Unterschied zwischen 30 Milliarden und einer Milliarde Milliarden. Die Funktion n*log n wächst nur wenig mehr als n selbst, n2 hat dagegen ein Wachstum, das schon die Grenzen unserer Vorstellung erreicht.
Programm
program mergesort;
const c=?;
type arr=array[1..c+1] of integer;
var v,temp:arr; i:integer;
procedure merge(i1,i2,j1,j2:integer);
var i,j,k,l:integer;
begin
i:=i1; j:=j1; l:=j2-i1+1;
for k:=1 to l do
if v[i]< v[j]
then begin
temp[k]:=v[i]; if i<i2 then i:=i+1 else i:=c+1; end
else begin
temp[k]:=v[j]; if j<j2 then j:=j+1 else j:=c+1; end;
for k:=1 to l do v[i1+k-1]:=temp[k];
end;
procedure msort(a,e:integer);
var a1,a2,e1,e2,t:integer;
begin
if e-a>1
then begin
a1:=a;
e1:=a + (e-a) div 2; a2:=e1+1; e2:=e;
msort(a1,e1);
msort(a2,e2);
merge(a1,e1,a2,e2);
end
else if v[a]>v[e] then
begin t:=v[a]; v[a]:=v[e]; v[e]:=t end;
end;
begin
for i:=1 to c do read(v[i]);
v[c+1]:=32767; msort(1,c);
end.
Wie wir gesehen haben, ist MergeSort bedeutend schneller als die beiden obigen Verfahren, hat aber den Nachteil, daß es einen temporären zweiten Array, also den doppelten Speicherplatz braucht.
Lochkartenmaschinen
MergeSort hatte übrigens früher eine weitere praktische Bedeutung.
In der Zeit, als man noch Lochkarten benützte, um seine Programme zu
schreiben und dann als Job beim Operator abgab, damit der das Programm auf
dem "Großrechner" rechnen ließ, benützte man Maschinen,
die große Lochkartenstapel durchblättern, lesen und mischen konnten.
Hier wurde MergeSort benützt, um einen Stapel Lochkarten zu sortieren.
Dies ging auf folgende Weise:
for i = 1 to
log n do begin
halbiere Stapel 1;
lege die Hälften in Stapel 2 und Stapel 3;
while Stapel 2 und Stapel 3 nicht leer do begin
mische die 2i untersten Karten von Stapel 2
und die 2i
untersten Karten von Stapel 3
auf richtige Weise in Stapel 1
end;
end
log n Mal mußte der Operator den Stapel in der Maschine teilen und umsetzen, die die beiden Teilstapel dann durchblätterte und wieder zu einem mischte. Das ging aber noch, denn bei einem Stapel von 1000 Karten, mußte er dies 10-mal tun, und größere Stapel hatte man kaum.
Beispiel:
1
| 2
| 5
| 8
3
| 1
|
4
| 7
5
| 7
|
2
| 6
8
| 3
|
1
| 5
2 2
1 | 5 5
2 | 8 8
5 | 4
7 7
3 | 4 4
1 | 7 7
4 | 3
4 4
5 | 8 8
7 | 6 6
2 | 2
6 6
8 | 6 6
3 | 3 3
1 | 1
_____________________________________________________________________
1 2
3 1
2 3
1 2 3
1 Stapel-Nr.
Sortieren durch Pivotieren: Quicksort
Idee:
Dies ist ebenfalls eine Divide-and-Conquer-Strategie. Aber im Gegensatz zu Mergesort ist nicht garantiert, daß wir das Problem halbieren. Darum ist der Aufwand im schlechtesten Fall (worst case) auch proportional zu n2 und nicht zu n*log n. Allerdings ist der Aufwand im Durchschnitt (average case) proportional zu n*log n und in vielen Messungen schneidet Quicksort besser ab als Mergesort. Außerdem benötigt Mergesort einen temporären zweiten Array, Quicksort aber nicht. Damit ist auch der Speicherbedarf von Quicksort geringer.
Man wählt unter den Elementen des zu sortierenden Arrays irgendein Element p - ein Pivotelement - das dazu dient, die Elemente des Arrays aufzuteilen in solche, die kleiner oder gleich p sind und solche, die größer p sind. Das günstigste Element wäre der Median, d.h. das Element, für das es ebensoviele kleinere, wie größere Elemente im Array gibt, das also unsere Arrayelemente in zwei gleich große Teilmengen aufteilt. Da wir aber nicht wissen, welches Element der Median ist, können wir auch jedes beliebige Element nehmen, etwa das erste im Array. Dieses ist genausogut, wie jedes andere, wie gut, hängt ganz von der zu sortierenden Folge ab. Es sei jedoch darauf hingewiesen, daß es sich lohnt, sich etwas mehr Mühe mit dem Pivotelement zu geben. So erziehlt man bessere Ergebnisse, wenn man als Pivotelement den Median der ersten 5 Elemente des Arrays wählt. Der Mehraufwand ist gering im Vergleich zum Gewinn.
Hat man den Array umgeschrieben in 2 Arrays - der eine enthält die Elemente kleiner oder gleich p, der andere die größer p - so sortiert man diese Teilarrays und legt sie aneinander: erst der Array mit den kleineren Elementen, dann das Pivotelement selbst und schließlich den zweiten Array. Dann haben wir einen sortierten Array vorliegen. Hier braucht man also nicht zu mergen, aber dafür ist das Teilen aufwendig: man braucht n-1 Vergleiche um einen Array der Länge n zu teilen.
Das Sortieren der Teilarrays geht genauso, sodaß wir wieder ein rekursives Verfahren haben. Allerdings benützen wir keinen temporären Array um diese Teilung vorzunehmen, sondern wir vertauschen die Elemente in unserem Array so, daß zuerst die Elemente kleiner oder gleich p kommen, dann p selbst und dann die übrigen. Dafür benützen wir 2 Zeiger. Ein Zeiger L läuft auf dem Array von links nach rechts und sucht das erste Element, das größer p ist. Bis zu dieser Stelle finden wir nur Elemente kleinergleich p vor, die in der richtigen linken Hälfte des Arrays liegen und nicht bewegt werden müssen. Genauso läuft eine Zeiger R von rechts nach links über den Array und sucht das erste Element, das kleinergleicht p ist. Auch hier gilt: rechts von der gefundenen Position liegen nur Elemente größer p, die somit schon in der richtigen Hälfte des Arrays liegen. Das Element unter L aber ist größer p und sollte nicht links von dem Element unter R liegen, das je kleinergleich p ist. Also tauschen wir diese beiden Elemente. Danach laufen die Zeiger L und R weiter aufeinander zu, bis wieder ein Tausch fällig wird oder sie sich kreuzen. Nach dem Kreuzen der beiden Zeiger sind wir mit dem Teilen fertig. Was bleibt, ist das Pivotelement zwischen die beiden Teilfolgen zu schieben. Dies geschieht, indem wir das Pivotelement, d.h. das erste Element des Arrays mit dem unter R liegenden Element tauschen.
Dasselbe wird nun mit den gewonnenen Teilarrays wiederholt, bis die Teilarrays ein Länge kleinergleich 2 haben. Diese kleinen Arrays sortieren wir, wenn nötig durch einen Vergleich. Dann sind wir fertig, denn alle Teilarrays liegen schon in der richtigen Folge hintereinander.
Programm
program quicksort;
const n = ?;
var a: = array[1..n] of integer;
i,j : integer;
procedure tausch(i,j: integer);
var temp: integer;
begin
temp := a[i];
a[i] := a[j];
a[j] := temp;
end;
procedure pivot(i,j: integer; var m: integer);
{i,j sind die Arraygrenzen, m das Feld, das den Array in
einen links davon und einen rechts davon teilt}
var p,L,R: integer; {p Pivotelement; Zeiger L sucht El > p, Zeiger R
sucht El <= p}
begin
p:= a[i]; L:= i; R:= j+1;
repeat L:= L+1 until (a[L] > p ) or (L >= j); {L
wandert nach rechts}
repeat R:= R-1 until a[R] <= p; {R wandert nach
links}
while L < R do begin {solange sich die Zeiger nicht
kreuzen}
tausch(L,R);
repeat L:= L+1 until a[L] > p;
{L wandert nach
rechts bis zum nä El > p. Das gibt es wegen tausch(L,R);}
repeat R:= R-1 until a[R] <= p; {R
wandert nach links}
end;
m:= R; {m ist das trennende Feld, die "Mitte"
}
tausch(i,m); {das Pivotelement kommt zwischen die beiden
Teilarrays}
end;
procedure quicksort(i,j: integer);
var m: integer;
begin
if j-i = 1 then if a[i] > a[j] then tausch(i,j);
if j-i > 1 then begin
pivot(i,j,m);
quicksort(i,m-1);
quicksort(m+1,j);
end;
end;
begin
quicksort(1,n);
end.
Aufwand
Man sieht schnell, daß der Aufwand etwa für einen Array mit umgekehrt sortierter Folge quadratisch in der Länge des Arrays ist: Das Pivotelement ist immer entweder das kleinste oder das größte Element des Arrays. Daher wird der Array überhaupt nicht geteilt, er wird nur kleiner, weil wir das Pivotelement herausnehmen. Es hat sich aber herausgestellt, daß dieses Verfahren dennoch im Durchschnitt sehr gut ist, besser als die bekannten Sortieralgorithmen, die nur mit Vergleichen arbeiten.
Wenn wir annehmen, daß jede Sortierung gleichwahrscheinlich ist, dann
läßt sich der Aufwand durch folgende Rekursionsformel beschreiben:
t(n) <= const*n + 1/n * Sumi=1,..,n (
t(i-1) + t(n-i) ). Eine Lösung dieser Ungleichung ist: t(n) = const*n*log
n . Dies ist also der durchschnittliche Aufwand unter der obigen Annahme.