In diesem Tutorial erkläre ich Ihnen, wie Sie den sogenannten „Bubblesort“ in PHP mit einem Array umsetzen. Der Bubblesort ist eine Sortierfunktion, die schrittweise die Elemente überprüft und von klein nach groß sortiert. Er wird auch als „Blasensortierung“ bezeichnet, da größere Elemente im Prozess nach oben steigen und kleinere nach unten sinken, was an das Aufsteigen von Blasen erinnert.
Beispiele, wo ein Bubblesort verwendet wird:
- Beim Sortieren einer Liste von Anzeigen in einer Online-Kleinanzeige.
- Beim Sortieren von Einträgen in einem Adressbuch.
- Sortieren von Ergebnissen in einer absteigenden Reihenfolge nach Punktzahl bei einem Spiel.
- Beim Sortieren einer Liste von Namen, alphabetisch.
Um den Bubblesort zu realisieren, verwende ich eine PHP Funktion, die Array-Elemente mit zwei For-Schleifen durchläuft. In diesen Schleifen prüfe ich mit einer IF Anweisung, ob das Element größer ist als das vorhergehende.
Nachfolgend das Beispiel:
<?php
/**
* @author Nico Schubert
* @copyright Copyright © 2011, Nico Schubert
*/
function bubblesort($bubblesort_array = array()) {
$anz = count($bubblesort_array);
$temp = '';
for ($a = 0; $a < $anz; $a++) {
for ($b = 0; $b < $anz - 1; $b++) {
if ($bubblesort_array[$b + 1] < $bubblesort_array[$b]) {
$temp = $bubblesort_array[$b];
$bubblesort_array[$b] = $bubblesort_array[$b + 1];
$bubblesort_array[$b + 1] = $temp;
}
}
}
return $bubblesort_array;
}
// Unsortiertes Array definieren
$bubblesort_array[] = '14';
$bubblesort_array[] = '8';
$bubblesort_array[] = '12';
$bubblesort_array[] = '1';
// Ausgabe des unsortierten Arrays
echo 'Ausgabe des unsortierten Arrays:';
echo '<pre>';
print_r($bubblesort_array);
echo '</pre>';
// Ausgabe des sortierten Arrays
echo 'Ausgabe des sortierten Arrays:';
echo '<pre>';
print_r(bubblesort($bubblesort_array));
echo '</pre>';
?>
Die Ausgabe würde folgendermaßen aussehen:
Ausgabe mit print_r(), des unsortierten Array:
Array ( [0] => 14 [1] => 8 [2] => 12 [3] => 1 )
Ausgabe des sortierten Array:
Array ( [0] => 1 [1] => 8 [2] => 12 [3] => 14 )
Erklärung:
Die Funktion bubblesort() nimmt ein Array als Parameter entgegen und sortiert es anschließend mittels des Bubblesort-Algorithmus. Der Algorithmus verteilt sich auf zwei verschachtelte Schleifen.
In der ersten Schleife wird die Anzahl der Elemente im Array bestimmt und in die Variable $anz gespeichert. Die Variable $temp dient als temporäre Variable, um das Element zu speichern, das zwischen zwei Array-Elementen getauscht wird. In der zweiten Schleife wird über jedes Element des Arrays iteriert und mit dem jeweils nächsten Element verglichen. Ist das nächste Element kleiner als das vorherige, werden beide miteinander vertauscht. Dieser Vorgang wird so lange wiederholt, bis alle Elemente des Arrays in der richtigen Reihenfolge liegen.
Optimierung des Bubblesort
Eine Möglichkeit, den Algorithmus effizienter zu gestalten, ist das Hinzufügen einer sogenannten Flag-Variable, die überwacht, ob in einer Iteration überhaupt Tauschvorgänge stattfinden. Falls kein Tausch vorgenommen wurde, bedeutet das, dass das Array bereits sortiert ist, und die Schleife kann frühzeitig beendet werden. Dies spart unnötige Durchläufe und verbessert die Leistung:
<?php
function optimierter_bubblesort($bubblesort_array = array()) {
$anzahl = count($bubblesort_array);
$temp = '';
for ($i = 0; $i < $anzahl; $i++) {
$getauscht = false;
for ($j = 0; $j < $anzahl - 1; $j++) {
if ($bubblesort_array[$j + 1] < $bubblesort_array[$j]) {
// Elemente tauschen
$temp = $bubblesort_array[$j];
$bubblesort_array[$j] = $bubblesort_array[$j + 1];
$bubblesort_array[$j + 1] = $temp;
$getauscht = true;
}
}
/* Wenn keine Elemente getauscht wurden, ist das Array sortiert */
if (!$getauscht) {
break;
}
}
return $bubblesort_array;
}
?>
Leistungsfähigkeit und Komplexität des Bubblesort
Der Bubblesort-Algorithmus hat im Durchschnitt und im schlimmsten Fall eine Laufzeitkomplexität von O(n²). Das bedeutet, dass die Anzahl der Vergleiche exponentiell ansteigt, je mehr Elemente das Array hat. Daher wird Bubblesort bei großen Datensätzen ineffizient. Für größere Arrays sind fortschrittlichere Algorithmen wie Quicksort oder Mergesort besser geeignet.
Vergleich mit anderen Sortieralgorithmen
Während Bubblesort leicht verständlich ist und für kleine Datensätze gut funktioniert, gibt es effizientere Alternativen wie Quicksort oder Mergesort. Diese Sortieralgorithmen haben im Durchschnitt eine bessere Laufzeitkomplexität von O(n log n) und werden bei großen Datenmengen bevorzugt.
Ich empfehle Ihnen noch alternativ den Beitrag zur: „Sortierung von Arrays“ anzusehen. Dort werden noch andere Möglichkeiten vorgestellt. Sollten Sie noch die ein oder andere Frage haben, so melden Sie sich einfach im Forum.
