ZFX
ZFX Neu
Home
Community
Neueste Posts
Chat
FAQ
IOTW
Tutorials
Bücher
zfxCON
ZFXCE
Mathlib
ASSIMP
NES
Wir über uns
Impressum
Regeln
Suchen
Mitgliederliste
Membername:
Passwort:
Besucher:
4396119
Jetzt (Chat):
31 (0)
Mitglieder:
5239
Themen:
24223
Nachrichten:
234554
Neuestes Mitglied:
-insane-
ZFX - C++ TutorialsDruckversion

Datensortierung in C++
Das C++ Tutorials von Joachim Weber aka Hippokrates erklärt wie Daten sortiert werden können.

© Copyright 2003 [whole tutorial] by Joachim Weber aka Hippokrates
Die Texte der Tutorials unterliegen dem Copyright und dürfen ohne schriftliche Genehmigung vom Author weder komplett noch auszugsweise vervielfältigt, auf einer anderen Homepage verwendet oder in sonst einer Form veröffentlicht werden. Die zur Verfügung gestellten Quelltexte hingegen stehen zur freien Weiterverwendung in Software Projekten zur Verfügung.
Die Quelltexte dieses Tutorials werden auf einer "as is" Basis bereit gestellt. Der Autor übernimmt keinerlei Garantie für die Lauffähigkeit der Quelltexte. Für eventuelle Schäden die sich aus der Anwendung der Quelltexte ergeben wird keinerlei Haftung übernommen.


Datensortierung in C++

Irgendwann kommt man meist in eine Situation, in der man gerne ein Array oder eine verkettete List sortiert hätte. Um für solche Situationen gewappnet zu sein, ist es natürlich wichtig, auch vernünftige Algorithmen zur Datensortierung zu kennen. 4 davon möchte ich in diesem Tutorial vorstellen. Ziel des ganzen, ist es eine Klasse zu entwickeln, die diese Möglichkeiten für uns kapselt. Damit ihr dann aber auch wisst, woran ihr mit diesen Methoden seid, habe ich auch noch getestet, wie schnell die einzelnen Algorithmen sind. Die Ergebnisse findet ihr weiter unten, zusammen mit dem Quellcode für dieses Tutorial.
Na dann, auf zum ersten Algorithmus.

Bubblesort

Bubblesort ist zugleich der einfachste, wie auch der langsamste Algorithmus. Ich stelle ihn hier aber trotzdem vor, denn er ist einen Blick wert, wenn man "nur mal eben schnell etwas sortieren will". Das Prinzip ist folgendes:

Das heißt wir laufen für jedes Element einmal durch das gesamte Array und vergleichen die
jeweils benachbarten Elemente (das Aktuelle mit seinem rechten Nachbarn). Wenn nötig, werden sie über den sog. Dreieckstausch vertauscht.
Dabei ist es im Prinzip egal, an welchem Ende des Arrays man beginnt.
Um das nochmal zu verdeutlichen gibt es jetzt erstmal ein Beispiel:
Wir haben ein Array [0, 5, 3, 2, 7], welches wir jetzt aufsteigend sortieren (d.h. von klein nach groß).
1. Durchgang:
[0, 3, 2, 5, 7]
2. Durchgang:
[0, 2, 3, 5, 7]
Damit ist die Liste bereits sortiert. Da der Algorithmus das aber nicht feststellen kann wird er auch noch die restlichen 3 Durchgänge vornehmen, ohne dass es etwas nutzen würde. Bereits beim ersten Durchgang, können die 5 und die 3 vertauscht werden, sodass das Array so aussieht: [0, 3, 5, 2, 7].
Dann werden die 5 und die 2 verglichen und vertauscht: [0, 3, 2, 5, 7]. Auch die 5 und die 7 werden verglichen, aber nicht mehr vertauscht (weil 5 < 7). An diesem Punkt wird auch klar, warum ich oben "für (alle_elemente - 1)" geschrieben habe. Die letzte Zahl im Array hat keinen linken Nachbarn, d.h. (Aktuell + 1) würde auf einen ungültigen Speicherbereich zugreifen. Da die letzte Zahl aber sowieso mit der vorletzten verglichen wird und von daher auch die Chance hat aufzusteigen, ist das kein Problem. Der Algorithmus heißt übrigens deshalb "Bubblesort", weil eine (in unserem Fall kleine) Zahl wie eine Blase im Array nach oben steigt. Damit das aber nicht nur so im Raum stehen bleibt, gibt es auch noch ein Code Beispiel:
int iArray[] = {0, 5, 3, 2, 7};

for(int i = 0; i < 5; i++) {
  for(int j = 0; j < (5 - 1); j++) {
    if(iArray[j] > iArray[j + 1]) {
      int iTemp = iArray[j];
      iArray[j] = iArray[j + 1];
      iArray[j + 1] = iTemp;
    }
  }
}
Einfach, oder ? Das ist aber nur die halbe Wahrheit. Im Informatikunterricht habe ich gelernt, wie man es noch schneller hinbekommen kann. Deshalb hier mal der Code einer optimierteren Version:
int iArray[] = {1, 4, 5, 2, 1};
int iSwapCount = 0;

for(int i = 0; i < 4; i++) {
  for(int j = 0; j < (5 - (i + 1)); j++) {
    if(iArray[j] > iArray[j + 1]) {
      int iTemp = iArray[j];
      iArray[j] = iArray[j + 1];
      iArray[j + 1] = iTemp;

      iSwapCount++;
    }
  }
  if(iSwapCount == 0) {
    break;
  }else {
    iSwapCount = 0;
  }
}
Hier wird also zum einen in der inneren Schleife nicht mehr das ganze Array durchlaufen, da wir ja nach einem Pass das größte Element schon an der letzten Position haben und zum anderen wird gezählt, wie oft vertauscht wurde. Wurde keinmal vertauscht, ist man schon mit Sortieren fertig. Die Idee dazu stammt von einem meiner Mitschüler. Diese Version ist im Gegensatz zur obigen zwar nicht so anschaulich, dafür aber deutlich schneller (4x so schnell mindestens).

Insertion Sort

Der nächste Algorithmus, den ich zeigen möchte, wird Insertion Sort genannt. Das Prinzip ist eigentlich sehr einfach zu verstehen. Wieder haben wir ein Array [0, 5, 3, 2, 7]. Dieses wird nun sortiert, in dem man das 1. Element, als eine sortierte Liste betrachtet, in die man ein Element einfügt. Da das wahrscheinlich etwas abstrakt klingt, werde ich das an einem Zahlenbeispiel demonstrieren. Der vertikale Strich "|" zeigt dabei das Ende der "sortierten Liste" an, in die eingefügt wird. [/code] 1: 0| 5 3 2 7
2: 0 5| 3 2 7
3: 0 3 5| 2 7
4: 0 2 3 5| 7
5: 0 2 3 5 7|
[/code] Wichtig ist, dass man sich diese "sortierte Liste" nicht bildlich vorstellt, denn wir haben ja keine 2. Liste sondern operieren direkt im Array. D.h. wir sortieren nicht direkt das gesamte Array, sondern immer einen Teil davon. Das Sortieren dieses Teiles funktioniert aber ähnlich wie Bubblesort. Naja, auf jeden Fall erstmal der Pseudocode:

Ich gebe zu, so ganz einfach ist das hier vielleicht doch nicht.
Deshalb noch mal etwas genauer:
Innerhalb der Schleife über alle Elemente des Arrays geschieht folgendes:
Solange der Index "ListenEnde" nicht 0 unterschreitet und das in Temp gespeicherte Element mit dem aktuell ausgewählten getauscht werden müsste (z.B. weil es größer ist) wird das aktuelle Element eine Position nach Rechts geschoben und ListenEnde dekrementiert.
Am Ende ist ListenEnde dann der Index, an dem ich Temp eintragen muss. Deshalb ist es auch so wichtig, dass Array[Zähler] in Temp gespeichert wurde, denn das ist der freie Platz, der mir zur Verfügung steht, die Elemente zu verschieben.
D.h. um von Schritt 1 nach Schritt 2 zu kommen (im Zahlenbeispiel oben) passiert Folgendes:
1. Die 0 wird mit der 5 verglichen (Zähler ist 1, ListenEnde ist 0)
2. Da die beiden nicht vertauscht werden müssen wird die 5 an ihrer Position belassen, denn 0 + 1 == 1.

Zähler wird dann um 1 hochgezählt und das ganze geht weiter:
1. Die 0 wird wieder mit der 5 verglichen -> nichts passiert
2. Die 5 wird mit der 3 vergleichen.
3. Diese beiden müssen vertauscht werden, also wird die 3 in Temp gespeichert. Die 5 wird dann an Position 2 gesetzt (da war vorher die 3). Da 0 und 3 aber nicht vertauscht werden, kann die 3 an Position an 1 gespeichert werden (da war vorher die 5).

Auf diese Weise wird das ganze Array dann sortiert. Man muss nur aufpassen, dass man auch bei 1 startet, sonst würde man das Element 0 mit sich selbst vergleichen... So, auch hier gibt es noch ein wenig Code, bevor es weitergeht:
int iArray[] = {0, 5, 3, 2, 7};
int iCurrentPos = 0;
int iTemp;

for(int i = 1; i < 5; i++) {
  iCurrentPos = i - 1;
  iTemp = iArray[i];
		
  while((iCurrentPos >= 0) && (Array[iCurrentPos] > Temp)) {
    Array[iCurrentPos + 1] = Array[iCurrentPos];
    iCurrentPos--;
  }
  Array[iCurrentPos + 1] = iTemp;
}
Der wichtigste Teil ist die while Schleife, da sie die Position berechnet, an der das Element eingefügt werden muss.

Selection Sort

Selection Sort ist wieder etwas einfacher gehalten. Im Prinzip geht es darum, sich das kleinste Element herauszusuchen und an den Anfang zu stellen. Dann fängt man eine Stelle weiter rechts an zu suchen und packt das so gefundene zweitgrößte Element an die 2. Position. Man geht also durch das Array und sucht sich aus den übrigen Elementen das kleinste aus und sortiert es an der aktuellen Position ein. Mit Zahlen sieht das so aus:
//0 ist am kleinsten<br>
1: 0 5 3 2 7<br>
//2 ist am kleinsten<br>
2: 0 2 5 3 7<br>
//3 ist am kleinsten<br>
3: 0 2 3 5 7<br>
Da das meine Meinung nach ein wirklich einfacher Algorithmus ist, zeige ich einfach mal den Code:
int iArray[] = {0, 5, 3, 2, 7}
int iMin;
int iMinIndex = 0;

for(int i = 0; i < 5; i++) {
  iMinIndex = i;
  iMin = iArray[iMinIndex];

  for(int j = (i + 1); j < 5; j++) {
    if(List[j] < Min) {
      iMinIndex = j;
      iMin = iArray[j];
    }
  }
  iArray[iMinIndex] = iArray[i];
  iArray[i] = iMin;
}
Der wichtige Teil liegt mal wieder innerhalb der inneren (for -) Schleife. Hier wird nämlich aus dem Reststück das kleinste Element gesucht. Hat man es gefunden, so kann man es nachher an der Stelle des aktuellen Elementes speichern. Also, eigentlich recht simpel.

Quicksort

Quicksort ist wahrscheinlich der komplizierteste der 4 Algorithmen. Dennoch ist es gut, wenn man ihn versteht, denn er heißt nicht umsonst Quicksort. Jedenfalls werden wir Schritt für Schritt vorgehen, weil es unter Umständen nicht ganz so leicht ist. Im Folgenden sind also die wichtigsten Schritte des Quicksort Algorithmus aufgelistet:
1. Man wähle ein willkürliches (!) Element aus dem Array (wird Pivot, oder Partition Element genannt)
2. Man sortiere das Array so, dass alle Werte, die kleiner als das Partition Element sind links davon stehen und alle die größer sind, rechts davon. (Vorausgesetzt, wir sortieren aufsteigend)
3. Das Array ist nun in 2 Hälften geteilt. Das Partition Element steht dabei schon an seiner finalen Position (schließlich wurde das Array ja nach ihm sortiert)
4. Für jede der beiden so entstandenen Hälften werden nun Schritte 1 - 4 ausgeführt.

Richtig, hier kommt Rekursion zum Einsatz. Für den Fall, dass ihr das aber noch nicht kennt, werde ich das auch erklären.

Rekursion:
In einer Programmiersprache muss man sich unter Rekursion eine Funktion vorstellen, die sich selbst aufruft. Das kann man leicht am Beispiel der Fakultät einer Zahl zeigen. Die Fakultät einer Zahl ist das Produkt aller Zahlen für die gilt: 0 < x <= Zahl. Da jede Rekursion auch mithilfe einer Schleife (weniger elegant) ausgedrückt werden kann, habe ich hier die Funktion zur Berechnung der Fakultät als Schleife und als Rekursion aufgeschrieben.

1. Die Schleife:
int iFakultaet = 0;
for(int i = iZahl; i > 0; i--) {
  iFakultaet *= i;
}
Einfach, oder?

2. Die Rekursion:
int iFakultaet = Fakultaet(iZahl);

int Fakultaet(int iZahl) {
  if(iZahl <= 1) {
    return 1;
  }else {
    return iZahl * Fakultaet(iZahl - 1);
  }
}
Zugegeben, in diesem Fall ist man mit der Schleife besser bedient, aber das Prinzip wird hier deutlich. Die Funktion ruft sich solange mit (iZahl - 1) selbst auf, bis die 1 erreicht ist. An diesem Punkt gibt die Funktion 1 zurück. Die Funktion in der Ebene darüber kann dann mit der 1 rechnen. D.h. das sieht ungefähr so aus:

Fakultaet(5) sieht auf dem Stack so aus:
1: 5 * Fakultaet(4)
2: 4 * Fakultaet(3)
3: 3 * Fakultaet(2)
4: 2 * Fakultaet(1)
5: 1
Die 1 wird dann zurückgegeben:

1: 5 * Fakultaet(4)
2: 4 * Fakultaet(3)
3: 3 * Fakultaet(2)
4: 2 * 1 = 2
5: 1

1: 5 * Fakultaet(4)
2: 4 * Fakultaet(3)
3: 3 * 2 = 6
4: 2 * 1 = 2
5: 1

1: 5 * Fakultaet(4)
2: 4 * 3 = 12
3: 3 * 2 = 6
4: 2 * 1 = 2
5: 1

1: 5 * 12 = 60
2: 4 * 3 = 12
3: 3 * 2 = 6
4: 2 * 1 = 2
5: 1
-> Fakultaet(5) ergibt 60. Mathematisch wird das übrigens als n! (sprich: n Fakultät) geschrieben.
Nun aber wieder zurück zum Quicksort Algorithmus. Dieser macht nämlich intensiven Gebrauch von der Rekursion. Ausnahmsweise zeige ich hier gleich den Quellcode:

Dieser Code ist etwas komplexer, deshalb einige Anmerkungen:
1. List ist ein Array (ein std::vector um genau zu sein)

2. SwapElements:
Die Funktion übernimmt 2 Zahlen, die Indizes in das übergebene Array (List) sind.
Sie dient dazu, die Elemente des Arrays die an diesen Positionen liegen zu vertauschen.

3. Compare:
Diese Funktion gibt true oder false zurück.
True bedeutet, dass die Elemente vertauscht werden müssen, false bedeutet, dass sie richtig sortiert sind.

Also, was macht das jetzt genau? Nun, es führt natürlich das aus, was oben in den 4 Schritten beschrieben wurde. Die Funktion übernimmt 2 Parameter, die angeben, in welchem Rahmen sie sich bewegen soll. Das brauchen wir, da wir den rekursiv aufgerufenen Versionen von Quicksort ja sagen wollen, welchen Teil des Arrays sie sich vornehmen sollen. Die Funktion überprüft also zuerst, ob die Low kleiner ist als High. Sind sie beispielsweise gleich, kann der Algorithmus gleich aufhören, denn das Ende wurde erreicht. Ist das aber nicht der Fall müssen 2 weitere Möglichkeiten unterschieden werden:
1. Die Elemente liegen direkt hintereinander:
Wenn sie direkt hintereinander liegen, können wir sie ggf. vertauschen und haben die unterste Ebene erreicht, weil man ja nicht weniger als 2 Zahlen sortieren kann.

2. Wir haben immer noch ein Stück Array vor uns, das länger ist als 2:
In diesem Fall wird es etwas komplizierter.
Um zu verstehen was dieser Abschnitt macht, müssen wir uns vor Augen halten, was das Ziel ist. Das Ziel ist es nämlich, das vorliegende Stück Array so zu sortieren, dass alle Elemente die kleiner sind als das Partition Element links davon und die größeren rechts davon liegen. Dazu suchen wir uns erstmal ein solches Partition Element. Ich habe hier das mittlere Element gewählt, aber die Wahl ist willkürlich. Wir speichern dann die Position des Elements in unserem Stück Array, sowie seinen Wert (zum Sortieren). Damit wir den Rest aber vernünftig sortieren können, stopfen wir das Partition Element in die oberste Position (und packen das Element, was da vorher war in die Mitte des Arrays). Anschließend beginnen wir eine Schleife. Diese soll so lange durchlaufen bis sich die Top und Bottom Indizes erreicht haben. In dieser Schleife suchen wir uns dann jeweils einen Wert der größer ist als das Partition Element und einen der kleiner ist, indem wir aus beiden Richtungen durch das Array laufen. Haben wir sie gefunden und die Indizes zeigen nicht auf dasselbe Element, so vertauschen wir die beiden. Auf diese Weise wird das Array dann in 2 Hälften gespalten (am Partition Element). Sind wir damit fertig, können wir auch unser Partition Element wieder in die Mitte setzen. Dabei setzen wir zwar ein Element ans Ende des Arrays, das da vielleicht garnicht hingehört (z.B. weil es kleiner ist als das Vorletzte), was aber egal ist, da wir das Array ja nicht endgültig sortieren. Für die beiden Hälften können wir dann den Quicksort Algorithmus durchführen. Schließlich erreichen wir dann einen Punkt, an dem wir nur noch 2 Elemente haben. Diese werden dann direkt sortiert (d.h. ggf. vertauscht).

Praktische Anwendung

Na dann, auf zum interessanten Teil. Jetzt haben wir die ganze trockene Theorie hinter uns und können mal was sinnvolles machen. Um diesen Teil zu verstehen, solltet ihr euch aber mit Templates und ein wenig mit der STL (Standard Template Library) auskennen. Hier schreiben wir nämlich eine Klasse, die das ganze Sortieren für uns machen wird - und zwar wird sie alles sortieren, was wir wollen. Um es nicht zu spannend zu machen, zeige ich euch einfach mal die Deklaration:
enum SortType {SORT_BUBBLE, SORT_QUICK, SORT_INSERT, SORT_SELECTION};

template<class Template>
class CSort {
  public:
    CSort() {}
    ~CSort() {}

     static void Sort(std::vector<Template> & List, bool (*Compare)(Template & r1, Template & r2), SortType Type);

  private:
    static void QuickSort(std::vector<Template> & List, DWORD dwLow, DWORD dwHigh, bool (*Compare)(Template & r1, Template & r2));

    static void BubbleSort(std::vector<Template> & List, bool (*Compare)(Template & r1, Template & r2));
	
    static void InsertionSort(std::vector<Template> & List, bool (*Compare)(Template & r1, Template & r2));
	
    static void SelectionSort(std::vector<Template> & List, bool (*Compare)(Template & r1, Template & r2));

    static void SwapElements(std::vector<Template> & List, DWORD dwFirstIndex, DWORD dwSecondIndex) {
      Template Temp;
      Temp = List[dwFirstIndex];
      List[dwFirstIndex] = List[dwSecondIndex];
      List[dwSecondIndex] = Temp;
    }
};
Wie ihr seht kommen hier die "allmächtigen" Templates zum Einsatz. D.h. wir können ein Array so sortieren:

So einfach ist das.
Wenn ihr euch jetzt nochmal den Quicksort Code anschaut, werdet ihr merken, dass der fast orginalgetreu aus der Klasse entnommen ist.
Die Sort Funktion entscheidet im Endeffekt nur, welche Funktion aufgerufen wird (an Hand des übergebenen Typs),

Mit dieser Klasse habt ihr jedenfalls ein wirklich mächtiges Werkzeug in der Hand, wenn es um das Sortieren geht. Wenn euch das aber noch nicht genug ist, hier noch ein paar Tips:
1. Es sollte ein leichtes sein, die Klasse auch "normale" Arrays sortieren zu lassen.
2. Man kann ohne Probleme weiter Algorithmen hinzufügen
3. Man könnte ein paar fertige Vergleichsfunktionen mitliefern

Dann noch ein Wort zu verketteten Listen.
Da gibt es 2 Möglichkeiten:
1. Ihr schreibt euch Funktionen, die auch verkettete Listen sortieren können.
2. Ihr nehmt einen std::vector und setzt ihn mit resize auf die Größe eurer Liste. Dann füllt ihr ihn mit Zeigern auf die einzelnen Knoten. Damit habt ihr dann ein Array, das ihr sortieren könnt. Und da die Funktion Compare ja von euch definiert werden kann, könnt ihr ohne weiteres auch Listenknoten sortieren.
Ist das Array dann einmal sortiert, müsst ihr es wieder in die Liste schreiben. Am Besten ist es, wenn ihr in euren Listenknoten nur Zeiger auf Objekte gespeichert habt, denn dann könnt ihr die Zeiger, die sich im Array befinden direkt in die Liste schreiben.

Bleibt noch eines: die Performance.
Um zu zeigen, welcher Algorithmus wie gut ist, habe ich Tests mit 1500, 3000 und 6000 Elementen gemacht. Auf einem Pentium 3(tm) 1000 Mhz ergab das folgende Ergebnisse:
Anzahl der Elemente Zeit in ms Quicksort Zeit in ms Bubble Sort Zeit in ms Insertion Sort Zeit in ms Selection Sort
1500 13 1280 305 345
3000 20 5070 1210 1385
6000 45 20475 4825 5690
Anhand dieser Zahlen kann man sich leicht für einen Algorithmus entscheiden, denn die Bearbeitungszeit wächst:
1. Bei Quicksort scheinbar linear (doppelt soviele Elemente -> doppelt so viel Rechenzeit)
Er ist es aber nur scheinbar, denn rechnet man es aus, so stellt man fest, dass seine Geschwindigkeit vom Logarithmus der Anzahl der zu sortierenden Elemente abhängig ist.
2. Bei Bubblesort steigt sie um das 4fache, wenn ich die Zahl der Elemente verdoppele
3. Bei Insertion Sort und Selection Sort vervierfacht sie sich auch, ist aber deutlich geringer

Von Bubblesort ist also abzuraten.
Wenn Quicksort aber so schnell ist, warum nimmt man den nich immer?
Nun, tut man in den meisten Fällen, aber es gibt eine Einschränkung: Wenn man zu viele Elemente hat, reicht der Stackspace nicht aus. Ihr erinnert euch, Quicksort arbeitet mit Rekursion und da jede Funktion ja Daten auf dem Stack hat, werden immer neue Daten hinzugefügt (durch das rekursive Aufrufen) bis der Algorithmus fertig ist, oder der Stack voll. Wenn es also um richtig große Mengen geht (eine Million z.B.) sollte man vielleicht besser Insertion oder Selection Sort nutzen.

Fazit

Tja, damit wäre es das dann auch. Mehr Algorithmen habe ich nicht zu bieten. Jetzt seid allerdings ihr am Zug und müsst mir möglichst viel Feedback geben. Das könnt ihr entweder im Board machen oder an meine Adresse schicken. Ihr könnt gerne Fragen stellen oder mich kritisieren bzw. auf Fehler hinweisen. Wenn ihr wollt könnt ihr auch Themenvorschläge für weitere Tutorials machen. Wichtig ist nur, dass ich erfahre, dass jemand mein Tutorial gelesen hat. Also, happy coding! Euer Hippokrates (aka Joachim Weber)


Informationen: " ); ?> " ); ?> " ); ?> " ); ?>
WWW :$wwwtitel
Data:Projektdateien
Mail:$author ($email)
Nick:$nick