Guten Tag !
Ich soll ein Referat in Pascal über ALLE Sortierverfahren außer Bubblesort halten. Dort soll ich Vergleiche machen zwischen den Sortierverfahren und wenn es möglich ist eine Tabelle finden !
Könnt ihr mir sagen wo ich die Infos finde oder könnt ihr mir ALLE Sortieverfahren in Pascal erklären ???
Für Antworten wäre ich dankbar
Moin Moin!
also… ich hab hier was in meinem Docus gefunden… iss aber n bisschen viel… aber zuerst n paar linkz:
N Bisschen Theorie und Geschwindigkeitsvergleiche:
http://www.wh-og.hs-niederrhein.de/~docx/docs/studiu…
Theorie und Code(nich ganz so schön):
http://www.hrz.uni-dortmund.de/A1/kurse/pascal99/tei…
Ich hoffe das hilft ein bisschen…
Gruß Torben
Eine einfache Frage, viele Antworten:
3.1. Bubblesort
Bubblesort ist einer der simpelsten Sortieralgorithmen. Die Idee dahinter ist die folgende: Im ersten Durchgang wird der Array vom Ende bis zum Anfang durchgegangen und in jedem Schritt das aktuelle Element mit dem nächsten verglichen. Ist das hintere kleiner, werden die beiden vertauscht, so daß größere Elemente am Weg liegenbleiben und das jeweils kleinste weiter nach vorn wandert. Am Anfang angekommen, liegt das kleinste Element des Arrays an Position 1, wo es auch hinsoll.
Im nächsten Durchlauf wird dann das zweitkleinste Element gesucht und nach vorne durchgereicht. Logischerweise muß dieser Durchlauf nicht ganz bis zum Anfang gehen, sondern nur bis Index 2. Im dritten Durchlauf braucht nur bis Index 3 gegangen zu werden usw, bis das Verfahren abgeschlossen ist.
Man kann sich vorstellen, daß die kleineren Elemente „leichter“ sind und daher aufsteigen wie Blasen - daher der Name Bubblesort. Ohne weitere Umschweife hier der Algorithmus:
procedure BubSort;
var
Run : LongInt;
Index : LongInt;
x : Byte;
begin
for Run := 2 to TableSize - 1 do
for Index := TableSize downto Run do
if Table[Index] Elem then
begin
Table[SmallInd] := Table[Elem];
Table[Elem] := Smallest;
end;
end;
end;
In der Variablen Smallest merkt sich der Algorithmus die Größe des bislang kleinsten Elementes, in SmallInd seine Position. Beide werden zunächst auf Elem initialisiert, d. h. auf die Position, die besetzt werden soll. Dann wird der übrige Array durchsucht, und wenn ein kleineres Element auftaucht, werden die beiden aktualisiert.
Zwei Besonderheiten sind beim Vertauschungsvorgang zu betrachten: Zum einen wird er nur ausgeführt, wenn tatsächlich eine neue Position gefunden wurde; zum anderen benötigen wir keinen Zwischenspeicher, weil der Wert des neuen Elementes ja noch in Smallest steht.
Selectionsort ist schneller als Bubblesort, - im allgemeinen kann man vom Faktor 2 ausgehen - für größere Arrays jedoch auch nicht besonders gut geeignet.
3.3. Insertionsort
Insertionsort steht für „Sortieren durch Einfügen“. Die Idee, die dem zugrunde liegt, ist einfach: Ein Teil am Anfang des Arrays, so wird angenommen, ist schon sortiert (zu Beginn ist dieser Teil natürlich 0 Elemente groß!). Nun wird das erste Element aus dem unsortierten Teil genommen und an der richtigen Stelle in den sortierten Teil eingefügt. Der sortierte Teil wächst dabei natürlich um ein Element, bleibt aber sortiert, wohingegen der unsortierte Teil um ein Element schrumpft.
Unser Algorithmus fängt also beim ersten Element an und geht dann bis zum letzten durch. Für jedes Element macht er nun folgendes: Von seiner Position aus bewegt er sich zum Anfang hin, solange die Elemente - wir sind ja im sortierten Teil - noch größer oder gleich dem in Frage stehenden Element sind. Dabei schiebt er jedes Element, daß er überquert, eins nach hinten, so daß er immer eine Lücke vor sich herschiebt. Findet er dann einen kleineren Kandidaten, schiebt er die Lücke nicht weiter, sondern setzt sein Element hinein. Auf diese Weise verbindet der Algorithmus die Suche nach der richtigen Position mit dem Verschieben der darüberliegenden Elemente.
procedure InsSortLinear;
var
Elem : LongInt;
x : Byte;
Index : LongInt;
begin
for Elem := 2 to TableSize do
begin
x := Table[Elem];
Index := Elem;
while (Index > 1) and (Table[Index - 1] >= x) do
begin
Table[Index] := Table[Index - 1];
Dec(Index);
end;
Table[Index] := x;
end;
end;
Wie man sieht, wird das Element zunächst in x gespeichert. Dann beginnt das Verschieben, bis entweder ein Element gefunden wird, das kleiner als x ist, oder bis man bei Index 1 angelangt ist. Im letzteren Fall hat man offenbar kein kleineres Element im sortierten Teil und plaziert das Element an Position 1.
Um die richtige Position zu finden, verwendet diese Version von Insertionsort eine lineare Suche. Da liegt die Idee nicht fern, das Verfahren dadurch zu beschleunigen, daß man eine binäre Suche verwendet. Das Verschieben der „dahinterliegenden“ Elemente muß dann gesondert erledigt werden.
procedure InsSortBinary;
var
Elem : LongInt;
L, R : LongInt;
Middle : LongInt;
Index : LongInt;
x : Byte;
begin
for Elem := 2 to TableSize do
begin
x := Table[Elem];
L := 1;
R := Elem;
while L x then R := Middle
else if Table[Middle] 0 do
begin
for Index := Gap + 1 to TableSize do
begin
j := Index - Gap;
while j > 0 do
begin
if Table[j] x do Dec(j);
if i j;
if Links i then QSort(i,Rechts);
end;
In x wird zunächst das herausgegriffene Element gespeichert - in diesem Fall die Mitte. i und j sind Laufindizes, die zunächst links und rechts positioniert werden. Dann marschieren sie von beiden Seiten aufeinander zu, bis sie ein Element finden, das nicht auf ihre Seite gehört. Sollten sie sich zu diesem Zeitpunkt nicht schon überholt haben (in dem Fall würde es ja wieder stimmen), tauschen sie die beiden Elemente aus und machen weiter. Das wiederholt sich so lange, bis sich die beiden erreicht bzw. überholt haben.
Anschließend wird QSort rekursiv aufgerufen, einmal für den unteren Teil, falls ein solcher überhaupt mit mehr als einem Element existiert, einmal für den oberen Teil (dito). Da die Rekursion nicht in der innersten Schleife stattfindet, ist sie relativ harmlos, allerdings kann das natürlich schon etwas auf den Stack gehen. Daher wird manchmal eine iterative Implementation empfohlen, bei der man den Stack selbst verwaltet; besonders trivial ist das leider nicht.
Quicksort ist, wie eingangs gesagt, in der Regel das schnellste Suchverfahren. Im schlimmsten Fall jedoch, wenn das herausgegriffene x jedesmal das größte (oder kleinste) Element des Arrays ist, fällt Quicksort leider auf das Niveau von Bubblesort herab. In den meisten Situationen fällt das nicht ins Gewicht, aber in Echtzeitanwendungen muß man es schon beachten.
3.6. Heapsort
Heapsort ist ebenfalls ein sehr schneller Algorithmus, aber im Durchschnitt nicht ganz so schnell wie Quicksort. Dafür leistet es sich auch im schlimmsten Fall keinen solchen Durchhänger wie dieses, so daß sich Heapsort vor allem für Anwendungen empfiehlt, in denen Höchstzeiten eingehalten werden müssen.
Die Funktionsweise ist leider nicht ganz trivial (finde ich). Man hat sich vorzustellen, daß die Elemente des Arrays tatsächlich in einem binären Baum gespeichert sind (näheres zu Bäumen findet sich übrigens auf meiner Seite über dynamische Datenstrukturen). Aber keine Angst, es kommt jetzt nicht die für binäre Bäume übliche Pointer-Orgie, denn es gibt einen Trick, mit dem man (ausgeglichene) binäre Bäume direkt im Array darstellen kann. Dazu stellen wir uns erstmal vor, Element 1 des Arrays sei die Wurzel des Baums. Und weiter gilt: Jedes Element des Arrays, z. B. i, ist ein Knoten des Baumes, und seine beiden Nachfolger sind die Elemente 2 · i und 2 · i + 1. Die folgende Abbildung verdeutlicht, wie die Knoten im Array liegen:
13,27,45,39,11,66,08
…13
…/\
…/…\
…/…\
…/…\
…27…45
…/…/\
…/…/…\
…39…11…66…08
Einen solchen Baum nennt man einen „Heap“ (engl. heap = Haufen), wenn jeder Knoten größer ist als seine Nachfolger. Die hintere Hälfte des Arrays - egal, in welchem Zustand er sich befindet - ist immer ein Heap, weil die Knoten ja gar keine Nachfolger mehr haben. Wenn der hintere Teil des Arrays (Hälfte oder mehr) ein Heap ist, kann ich diesen um ein Element nach vorne erweitern. Damit das Ergebnis immer noch ein Heap ist, muß ich das Element am neuen Knoten allerdings im Baum „absinken“ lassen (engl. to sift = sieben), wobei es immer mit dem größeren seiner Nachfolgeknoten vertauscht wird - so lange, bis beide Nachfolgeknoten kleiner sind.
Dieser Vorgang wird von der Prozedur Sift erledigt; wir werden ihn noch öfter brauchen:
procedure Sift(L, R : LongInt);
var
i, j : LongInt;
x : Byte;
begin
i := L;
j := 2 * L;
x := Table[i];
if (j Table[j]) then Inc(j);
while (j x) do
begin
Table[i] := Table[j];
i := j;
j := j * 2;
if (j Table[j]) then Inc(j);
end;
Table[i] := x;
end;
Wie man sieht, bekommt Sift eine linke Grenze, dort fängt es an, und eine rechte Grenze, an der es aufhört - auch wenn der Array vielleicht noch weiterginge (es ist jetzt noch etwas unklar, wozu das gut sein soll: Geduld!). In x wird der Wert des zu „siftenden“ Elements gespeichert, i ist der aktuelle Knoten und j der Nachfolgeknoten - entweder 2 · i oder, wenn größer, 2 · i + 1.
Der erste Teil von Heapsort besteht genau darin, wie beschrieben von der Hälfte ausgehend den Heap nach vorne zu erweitern, bis der ganze Array ein Heap ist. Der zweite Teil, das eigentliche Sortieren, ist nun eigentlich auch nicht mehr schwer zu verstehen: Das erste Element des Arrays ist, weil es die Wurzel eines Heaps ist, das größte Element. Es gehört also ans Ende des Arrays. Setzen wir es doch einfach dorthin, indem wir es mit dem dortigen Element austauschen. Dieses ist nun an Position 1. Wir lassen es mit Hilfe von Sift einsinken - natürlich nur bis zum vorletzten Element, das letzte wollen wir in Ruhe lassen - und haben anschließend wieder das Maximum an Position 1 (weil die Knoten der zweiten Ebene ja auch die Maxima ihrer Unterheaps sind). Dieses vertauschen wir nun mit dem Element an vorletzter Stelle, lassen die neue Nummer 1 einsinken usw. usf. Wenn wir den ganzen Array besetzt haben, sind wir fertig, und weil der Array von unten her mit den jeweils größten Elementen aufgefüllt wurde, ist er sortiert - voilá!
Der Heapsort-Algorithmus in Pascal, die beiden Teile sind durch eine Leerzeile getrennt:
procedure HSort;
var
L, R : LongInt;
Index : LongInt;
x : Byte;
begin
L := (TableSize div 2) + 1;
R := TableSize;
while (L > 1) do
begin
Dec(L);
Sift(L,R);
end;
for Index := R downto 1 do
begin
x := Table[1];
Table[1] := Table[Index];
Table[Index] := x;
Sift(1,Index - 1);
end;
end;
Nun wird auch deutlich, warum Sift auch eine rechte Grenze mitbekommt. Eine mögliche Verbesserung besteht darin, daß man den Code von Sift gleich direkt in den Heapsort-Algorithmus schreibt. Dies sollte kein großes Problem sein, nur mit den Variablennamen muß man ein bißchen aufpassen.
Ganz schön viel Aufwand für einen Sortieralgorithmus, könnte man sagen. Andererseits ist es halb so schlimm, wenn man es einmal verstanden hat. Und der Trick mit dem Unterbringen von binären Bäumen in Arrays ist ja auch etwas, das man sich merken kann.
3.7. Bucketsort
Hörte es sich bis jetzt so an, als wären Quicksort und Heapsort die schnellsten Suchverfahren, so wirkt es vielleicht verwunderlich, aber das eher selten anzutreffende Bucketsort verspricht, noch schneller zu sein. Die Sache hat - natürlich - einen Haken: Bucketsort benötigt zusätzlichen Platz. Und zwar umso mehr, je größer die Menge der möglichen Schlüssel ist. Warum das so ist, wird gleich deutlich.
Das Prinzip ist einfach: In einem zusätzlichen Array namens Bucket gibt es für jeden möglichen Schlüssel ein „Fach“. Dann wird der Array Table von vorn bis hinten durchgegangen, und jedes Element wird in sein Fach gelegt. Anschließend braucht man nur noch den Inhalt er Fächer nacheinander zurück in den Array zu kopieren; dabei sollten die Fächer natürlich in der richtigen Reihenfolge sein. Anschließend ist der Array sortiert.
Leider ergibt sich eine Reihe von Problemen: Wie z. B. speichere ich mehrere Elemente in einem Feld des Bucket-Arrays? Diese Elemente müssen ja nicht unbedingt gleich sein, sie haben nur den gleichen Sortierschlüssel! Hierfür gibt es verschiedene Lösungen, aber die naheliegendste ist, eine linked List zu verwenden.
Zum anderen möchte man häufig Strings sortieren, aber selbst von Strings der Länge 10 gibt es 2610 = 1.411671 · 1014 Möglichkeiten. Von Standard-Strings der Länge 255 will ich mal lieber gar nicht anfangen… Auch das Sortieren von LongInts mit ihren 32 Bit Länge dürfte wenig spaßig sein. Ein Ausweg besteht darin, den Schlüssel in seine Einzelelemente aufzuteilen und mehrmals zu sortieren; bei Strings wird also zuerst nach dem letzten Zeichen sortiert, dann nach dem vorletzten usw. Bei Zahlen kann man entsprechend nach einzelnen Bits sortieren.
Um den Algorithmus zu verdeutlichen, will ich aber ein viel simpleres Beispiel nehmen: Es werden Bytes sortiert, der Bereich, innerhalb dessen sie Werte annehmen dürfen, ist also 0 bis 255. Eine starke Vereinfachung besteht darin, daß die Zahlen nur aus dem Schlüssel bestehen können, und zwei Elemente mit dem gleichen Schlüssel nicht unterscheidbar sind. Daher brauchen sie nicht in den Fächern gespeichert zu werden - der Index des Faches ist schon der Wert, und im Fach wird einfach gezählt, wie oft die betreffende Zahl schon aufgetreten ist. So oft wird sie dann beim Zurückschreiben in den Array wiederholt.
Und so sieht die Prozedur aus:
procedure BuckSort;
var
Index : LongInt;
BuckIndex : LongInt;
begin
for BuckIndex := 0 to 255 do Bucket[BuckIndex] := 0;
for Index := 1 to TableSize do
Inc(Bucket[Table[Index]]);
Index := 1;
BuckIndex := 0;
while Index j;
if L i then QSort(i,R);
end;
begin
QSort(0,High(Table));
end;
Damit kann man nun alles sortieren, was man will; man muß sich nur die Mühe machen, für alle Elemente Pointer zu haben. Entweder verwaltet man die Elemente dynamisch, oder man legt sie in einem Array ab und setzt dann in einem zweiten Array gleicher Länge in jede Zelle i einen Pointer auf Element i des ursprünglichen Arrays.
Eine Sortier-Unit sowie ein Demoprogramm, welches die Unit benutzt, sind in den folgenden beiden Dateien zu finden:
genpurquick.pas
gpqdemo.pas
4.2. Effizientes Sortieren von Strings mit Bucketsort:
Die unter 3.7. beschriebene Version von Bucketsort ist von eher akademischen Nutzen. Während die Tatsache, daß in den Beispielen nur Zahlen sortiert werden, bei den anderen Algorithmen nicht weiter stört, weil man sie leicht auf andere Typen umstellen kann, geht dies bei Bucketsort leider nicht so einfach. In diesem Abschnitt wird an einem Beispiel gezeigt, wie Bucketsort mit Daten umgeht, die nicht nur aus ihren Schlüsseln bestehen. Gleichzeitig wird der im gleichen Abschnitt erwähnte Trick demonstriert, Strings in mehreren Durchgängen zu sortieren.
Um mehrere Elemente in einem Bucket abzulegen, gibt es verschiedene Möglichkeiten. Hier habe ich mich für die Verwendung dynamischen Speichers in Form einer Linked List entschieden. Die Elemente müssen aus dem Bucket in der gleichen Reihenfolge herausgeholt werden, in der sie auch hereingekommen sind - eine klassiche Warteschlange. Da lag es nahe, meine Queue-Unit in die Pflicht zu nehmen. Genauere Informationen über diese Unit sind auf dieser Seite zu finden; für dieses Beispiel reicht es aber auch, folgendes zu wissen:
Die Elemente, die in der Queue gespeichert werden, sind Pointer. Die Strings müssen also, entweder grundsätzlich oder ad hoc in der Sortierprozedur, in dynamischem Speicher aufbewahrt werden. Die Unit Queue stellt einen Typen TQueue bereit, sowie die Aufrufe Enqueue (Einfügen eines Elementes), Dequeue (Herausholen) und IsEmpty (True, wenn die Queue leer ist, False sonst).
Die Methode, ganze Strings mit nur 26 Fächern zu sortieren, wurde schon in 3.7. beschrieben: Zuerst werden sie nach dem letzten Zeichen sortiert, dann nach dem vorletzten usw. Das geht natürlich nur gut, wenn der Algorithmus die Reihenfolge von Elementen mit dem gleichen Schlüssel beibehält (man sagt dann, er ist „stabil“), was Bucketsort auch tut. Weiterhin ist wichtig, daß alle Strings gleich lang sind. Folgende Deklarationen werden gebraucht:
const
StrMax = 8;
type
PSortStr = ^TSortStr;
TSortStr = String[StrMax];
var
Table : Array[1…TableSize] of TSortStr;
Bucket : Array[‚a‘…‚z‘] of TQueue;
Damit sieht die Sortierprozedur dann so aus:
procedure SBuckSort;
var
Run : LongInt;
Index : LongInt;
SortStr : PSortStr;
c : Char;
begin
for Run := StrMax downto 1 do
begin
for Index := 1 to TableSize do
begin
New(SortStr);
SortStr^ := Table[Index];
Enqueue(Bucket[Table[Index][Run]],SortStr);
end;
c := ‚a‘;
for Index := 1 to TableSize do
begin
while IsEmpty(Bucket[c]) do Inc©;
SortStr := Dequeue(Bucket[c]);
Table[Index] := SortStr^;
Dispose(SortStr);
end;
end;
end;
Beeindruckend, wie sehr es immer noch der Ursprungsversion ähnelt. Statt des Inc und Dec auf dem Bucket haben wir jetzt Enqueue und Dequeue, und die Prüfung, ob der Bucket 0 sei, wird durch IsEmpty ersetzt.