Sortieren gehört in der Informatik zu einer der Paradedisziplinen und es ist allgegenwärtig, sei es in Tabellenkalkulationen, in Datenbanken oder im Web. Jede höhere Programmiersprache bietet mindestens eine Methode zum Sortieren schon vorgefertigt an. Man kommt also mit den eigentlichen Algorithmen gar nicht in "Berührung". Als Programmierer / Informatiker sollte man diese Verfahren aber zumindest gesehen, am Besten einmal selbst implementiert haben.
Die folgenden Verfahren sind in PHP programmiert, können aber mit grundlegenden Kenntnissen in eine beliebige andere Programmiersprache portiert werden. Zu jedem Verfahren ist die Laufzeitkomplexität (Average Case) in Abhängigkeit zur Eingabegröße n in Landau-Notation, also zur Anzahl der zu sortierenden Werte, angegeben. Des Weiteren ist angegeben, ob es sich bei dem Verfahren um ein sogenanntes In-Situ-Verfahren handelt, d.h. ob die Sortierung auf dem gegebenen Array stattfindet (in-situ) oder ob ein zweites Array im Speicher angelegt werden muss, in das die sortierte Folge oder Teilergebnisse gespeichert werden (nicht in-situ). Als Drittes ist vermerkt, ob der Algorithmus ein stabiles Sortierverfahren ist, sprich ob die Reihenfolge gleicher Werte nach der Sortierung erhalten bleibt oder nicht (nicht stabil).
Allgemeine Methoden
Um den Code ein wenig schlanker zu gestalten, sind die Methode swap() (Vertauschen zweier Array-Elemente) und die Methode print() (Ausgabe des Arrays) implementiert worden.
private static function swap(&$array, $index1, $index2) {
$temp = $array[$index1];
$array[$index1] = $array[$index2];
$array[$index2] = $temp;
}
private static function printArray(&$array) {
echo '<p>' . implode(', ', $array) . '</p>';
}Selection Sort
Durchlaufe das Array von links nach rechts und vergleiche den Wert des aktuellen Elements mit dem Minimum aus dem rechten Teilarray. Ist das Minimum kleiner als der aktuelle Wert, so tausche beide Elemente. Gehe ein Element weiter und führe den Algorithmus erneut durch. Beende den Algorithmus sobald das vorletzte Element abgearbeitet ist.
public static function selectionSort(&$array) {
for ($i = 0; $i < count($array) - 1; $i++) {
// find the minimal element and save its value and its position
$min = $array[$i];
for ($j = $i + 1; $j < count($array); $j++) {
if ($array[$j] < $min) {
$min = $array[$j];
$pos = $j;
}
}
// if there was an element with a value lower than the value of the
// element to check, swap it
if ($min != $array[$i]) {
$array[$pos] = $array[$i];
$array[$i] = $min;
}
self::printArray($array); // print for testing tool
}
}Eigenschaften des Selection Sort Algorithmus:
- Laufzeitkomplexität: O(n2)
- Speicherbedarf: In-Situ-Verfahren
- Sortierung: stabil
Bubble Sort
Durchlaufe das Array von links nach rechts und vergleiche jeweils zwei benachbarte Elemente. Ist der Wert des linken Elements größer als der Wert des rechten Elements, so tausche die Elemente. Nach dem ersten Durchlauf steht somit das Element mit dem größten Wert ganz rechts. Führe den Algorithmus nun auf dem unsortierten Teilarray für Element 1 bis Element n-1 aus, dann von 1 bis n-2, usw. bis das zu sortierende Teilarray die Länge 1 hat.
public static function bubbleSort(&$array) {
for ($i = 0; $i < count($array) - 1; $i++) {
for ($j = 0; $j < count($array) - $i - 1; $j++) {
if ($array[$j] > $array[$j + 1]) {
self::swap($array, $j + 1, $j);
}
self::printArray($array); // print for testing tool
}
}
}Eigenschaften des Bubble Sort Algorithmus:
- Laufzeitkomplexität: O(n2)
- Speicherbedarf: In-Situ-Verfahren
- Sortierung: stabil
Insertion Sort
Durchlaufe alle Elemente des Arrays von links nach rechts beginnend mit dem Element mit Index 1 (der Startindex ist 0) und halte das Element fest. Das festgehaltene Element habe ab jetzt den Namen A. Vergleiche nun den linken Nachbarn von A mit A. Ist der Nachbar (B) größer als A so schiebe ihn im Array um eine Position nach rechts. Wiederhole dies mit dem ehemals linken Nachbarn von B, solange bis A nicht kleiner als der Vergleichspartner (C) ist. Füge dann A rechts von C in das Array ein.
Der Algorithmus ähnelt stark dem Sortieren einer Hand bei einem Kartenspiel. Man nimmt eine Karte heraus und fügt sie an der richtigen Stelle wieder ein, solange bis die Hand komplett sortiert ist.
public static function insertionSort(&$array) {
for ($i = 1; $i < count($array); $i++) {
// get element
$element = $array[$i];
$j = $i;
// move elements one place to the right while the
// current element is smaller than the element to
// be checked
while ($j > 0 && $array[$j - 1] > $element) {
$array[$j] = $array[$j - 1];
$j--;
}
// insert current element in the array on the right position
$array[$j] = $element;
self::printArray($array); // print for testing tool
}
}Eigenschaften des Insertion Sort Algorithmus:
- Laufzeitkomplexität: O(n2)
- Speicherbedarf: In-Situ-Verfahren
- Sortierung: stabil
Bucket Sort
Der Bucket Sort Algorithmus ist ein spezieller Sortieralgorithmus. Er funktioniert nur für ganzzahlige Werte, dafür sortiert er aber in linearer Laufzeit. In der folgenden Implementierung ist die Laufzeit O(max - min), also der Abstand zwischen dem größten und dem kleinsten Element im Array. Für die Sortierung von vielen Werten in einer engen Wertemenge ist dieser Algorithmus ideal. Für die Sortierung von wenigen weit verstreuten Werten hingegen nicht.
Berechne den kleinsten (min) und größten Wert (max) des Arrays. Initialisiere nun ein Array der Größe max - min. Durchlaufe das originale Array und speichere die Anzahl des aktuellen Werts im neuen Array am Index aktueller Wert - min. Min wird abgezogen um nur positive Indizes ab 0 zu erhalten. Das neue Array bildet ein Histogramm über die Werte des originalen Arrays. Durchlaufe nun das Histogramm von links nach rechts und schreibe die Indizes des Histogramms in das originale Array. Wiederhole dies mit dem gleichen Index so oft, wie der Wert des Histogramms an diesem Index ist.
public static function bucketSort(&$array) {
$min = $array[0];
$max = $array[0];
// get min and max
for ($i = 1; $i < count($array); $i++) {
if ($array[$i] > $max)
$max = $array[$i];
if ($array[$i] < $min)
$min = $array[$i];
}
// initialize histogram array with a size of max-min
$histogram = array($max - $min);
for ($i = 0; $i < count($array); $i++) {
$histogram[$array[$i] - $min] = 0;
}
// increment histogram at any index of the array-min
// calculate an offset with min to get only index with
// non-negative numbers
for ($i = 0; $i < count($array); $i++) {
$histogram[$array[$i] - $min]++;
}
// loop over histogram and save each index in array
$k = 0;
for ($i = 0; $i <= $max - $min; $i++) {
if (isset($histogram[$i])) {
for ($j = 0; $j < $histogram[$i]; $j++) {
$array[$k++] = $i + $min;
}
}
}
}Eigenschaften des Bucket Sort Algorithmus:
- Laufzeitkomplexität: O(|max - min|)
- Speicherbedarf: Kein In-Situ-Verfahren
- Sortierung: stabil
Quick Sort (rekursiv)
Sogenannter "Zwei-Zeiger"-Algorithmus. Wähle als Pivot-Element das mittlere Element des Arrays. Setze Zeiger 1 an den Anfang, Zeiger 2 an das Ende des Arrays. Ist das Element, auf das Zeiger 1 zeigt, größer als das Pivot-Element, dann bleibe mit Zeiger 1 stehen, ansonsten rücke um eine Position nach rechts. Ist das Element, auf das Zeiger 2 zeigt, kleiner als das Pivot-Element, dann bleibe mit Zeiger 2 stehen, ansonsten rücke um eine Position nach links. Verharren beide Zeiger so tausche die Elemente, rücke Zeiger 1 nach rechts und Zeiger 2 nach links. Fahre so fort bis sich die Zeiger gekreuzt haben. Nun sind alle Elemente kleiner als das Pivot-Element links und alle größeren Elemente rechts. Wende nun den Algorithmus für die beiden Teilarrays an. Der Algorithmus endet, wenn die Teilarrays Länge 1 haben.
// wrapper function to hide index parameters
public static function quickSort(&$array) {
self::quickSortRec($array, 0, count($array) - 1);
}
private static function quickSortRec(&$array, $left, $right) {
$i = $left;
$j = $right;
// get middle of the array
$middle = intval(($left + $right) / 2);
// set middle element as pivot element
$pivot = $array[$middle];
// while pointers did not cross
do {
// go right while element < pivot
while ($array[$i] < $pivot) $i++;
// go left while element > pivot
while ($array[$j] > $pivot) $j--;
// if pointers did not cross
if ($i <= $j) {
self::swap($array, $i, $j);
// move pointer to the right element
$i++;
// move pointer to the left element
$j--;
}
} while ($i <= $j);
self::printArray($array); // print for testing tool
// sort left array
if ($left < $j) self::quickSortRec($array, $left, $j);
// sort right array
if ($i < $right) self::quickSortRec($array, $i, $right);
}Eigenschaften des Quick Sort Algorithmus:
- Laufzeitkomplexität: O(n*log(n))
- Speicherbedarf: In-Situ-Verfahren
- Sortierung: nicht stabil
Quick Sort (iterativ)
Quick Sort iterativ funktioniert nach dem Prinzip des rekursiven Quick Sort Verfahrens. Einzig die rekursiven Funktionsaufrufe werden durch eine Schleife und einen Stack gelöst. Auf dem Stack werden die Grenzindizes der Teilarrays gespeichert. Das Array wird also wieder in kleinere Teilprobleme aufgeteilt (Grenzen auf den Stack pushen) und dann wieder zusammengesetzt (Grenzen vom Stack mit pop nehmen).
public static function quickSortIterative(&$array) {
// initialize variables
$left = 0;
$right = count($array) - 1;
$stack = array();
array_push($stack, $left);
array_push($stack, $right);
// do sorting while stack is not empty
while (!empty($stack)) {
// get initial right and left pointer from stack
$right = array_pop($stack);
$left = array_pop($stack);
// get pivot element (element in the middle) from partial field
$middle = intval(($left + $right) / 2);
$pivot = $array[$middle];
// set pointers to temporarily variables
$i = $left;
$j = $right;
// push and swap while pointers do not cross
do {
// push left pointer from left to right, while value is smaller than value of pivot
while ($array[$i] < $pivot) $i++;
// push right pointer from right to left, while value is bigger than value of pivot
while ($array[$j] > $pivot) $j--;
// swap elements, if left element is bigger and right element is smaller than pivot
if ($i <= $j) {
self::swap($array, $i, $j);
self::printArray($array); // print for testing tool
// push pointers
$i++;
$j--;
}
} while ($i <= $j);
// push bounds of left partial field side on stack
if ($left < $j) {
array_push($stack, $left);
array_push($stack, $j);
}
// push bounds of right partial field on stack
if ($i < $right) {
array_push($stack, $i);
array_push($stack, $right);
}
}
}Eigenschaften des iterativen Quick Sort Algorithmus:
- Laufzeitkomplexität: O(n*log(n))
- Speicherbedarf: In-Situ-Verfahren + Stack
- Sortierung: nicht stabil
Merge Sort
Ein weiterer Divide-and-Conquer-Algorithmus. Teile das Array solange in zwei gleich große Teile bis die Teilprobleme trivial zu lösen sind. Füge nun zwei benachbarte Teilarrays wieder zu einem sortierten Array zusammen, bis das Array komplett sortiert ist.
// wrapper function to hide index parameters
public static function mergeSort(&$array) {
self::mergeSortRec($array, 0, count($array) - 1);
}
private static function mergeSortRec(&$array, $left, $right) {
if ($left < $right) {
// split the array in the middle
$middle = intval(($left + $right) / 2);
self::mergeSortRec($array, $left, $middle);
self::mergeSortRec($array, $middle + 1, $right);
// merge the two sorted arrays to one sorted array
self::merge($array, $left, $middle, $right);
}
}
private static function merge(&$array, $left, $middle, $right) {
$helpArray = array();
$i = 0;
$j = $left;
while ($j <= $middle) {
$helpArray[$i++] = $array[$j++];
}
$i = 0;
$k = $left;
while ($k < $j && $j <= $right) {
if ($helpArray[$i] <= $array[$j])
$array[$k++] = $helpArray[$i++];
else
$array[$k++] = $array[$j++];
}
while ($k < $j) {
$array[$k++] = $helpArray[$i++];
}
self::printArray($array); // print for testing tool
}Eigenschaften des Merge Sort Algorithmus:
- Laufzeitkomplexität: O(n*log(n))
- Speicherbedarf: Kein In-Situ-Verfahren
- Sortierung: stabil
Heap Sort
Wandele das Array in die Datenstruktur Heap (ein Binärbaum, bei dem die Kind-Elemente immer kleiner als das Eltern-Element ist) um. Die Umwandlung findet direkt auf dem gegebenen Array statt (In-Situ-Verfahren). Somit ist das erste Element des Heaps das größte Elements des Arrays. Tausche nun das letzte Element des Arrays mit dem Ersten. Das Array ist nun bis zur Stelle n - 1 unsortiert und an der Stelle n sortiert. Baue nun im Teilarray von Index 1 bis n - 1 wieder einen Heap und tausche das erste Element mit dem (n - 1)-ten Element. Das unsortierte Teilarray reicht nun von Index 1 bis n - 2. Die Stellen n - 1 und n sind sortiert. Fahre so fort bis das komplette Array sortiert ist.
public static function heapSort(&$array) {
// Build a heap by the given $array
self::createHeap($array);
self::printArray($array); // print for testing tool
$count = count($array);
for ($i = 1; $i < $count; $i++) {
$len = $count - $i;
// Swap root node A with the right leaf and write A to the result array
self::swap($array, 0, $len);
self::printArray($array); // print for testing tool
// Let the root node swap until a new heap is recreated
self::downHeap($array, $len);
self::printArray($array); // print for testing tool
}
}
private static function createHeap(&$array) {
for ($j = count($array); $j > 0; $j = intval($j / 2)) {
for ($i = count($array) - 1; $i > 0; $i--) {
$indexFather = intval(($i - 1) / 2);
// check if value of the father element is smaller than the
// value of the child element. true -> swap them
if ($array[$i] > $array[$indexFather]) {
self::swap($array, $i, $indexFather);
}
}
}
}
private static function downHeap(&$array, $len) {
$k = 0;
while(true) {
// get left and right child of node k
$indexLeftChild = $k * 2 + 1;
$indexRightChild = $k * 2 + 2;
// if node k is a leaf, the heap is recreated
if (($indexLeftChild < $len
&& $indexRightChild < $len
&& $array[$indexLeftChild] < $array[$k]
&& $array[$indexRightChild] < $array[$k])
|| $indexRightChild >= $len) {
return;
}
// left child is bigger than right child, swap node k with
// left child
if ($array[$indexLeftChild] >= $array[$indexRightChild]) {
self::swap($array, $indexLeftChild, $k);
$k = $k * 2 + 1;
// right child is bigger than left child, swap node k with
// right child
} else {
self::swap($array, $indexRightChild, $k);
$k = $k * 2 + 2;
}
}
}Eigenschaften des Heap Sort Algorithmus:
- Laufzeitkomplexität: O(n*log(n))
- Speicherbedarf: In-Situ-Verfahren
- Sortierung: nicht stabil
Tool zum Testen der Verfahren
Anmerkung: Es wird das Array in Teilschritten vom unsortierten zum sortierten Array ausgegeben. Die Anzahl der Ausgaben gibt keine Auskunft über die Laufzeitkomplexität des Algorithmus, da die Methode print() in den Verfahren an unterschiedlichen Positionen innerhalb der Schleifen steht.
Changelog
- 26.01.2015: Änderung des Insertion-Sort Verfahrens zu einem In-Situ-Verfahren.
