Navigation
 Startseite
 Fachbücher
 Forum
 Webmaster News
 Script Newsletter
 Kontakt
 Script Installation
 Php
 Php Tutorials
 Impressum

Community-Bereich
 kostenlos Registrieren
 Anmelden
 Benutzerliste

Script Datenbank
 Script Archiv
 Script Top 20
 Screenshots
 Testberichte

Suche
 

Unsere Php Scripts
 Counter Script
 Umfrage Script
 Bilder Upload Script
 Terminverwaltung
 Simple PHP Forum
 RSS Grabber

Script Mods
 phpBB Adsense Mode

Tools und Generatoren
 .htpasswd Generator
 md5 Generator
 base64 Generator
 ICQ Generator
 Colorpicker
 Unix timestamp Tool
 TLD Liste
 Webkatalog‑Verzeichnis

Partner
 Sprüche Treff

Artfiles.de
Bietet Serviceorientierte Internetdienstleistungen...
https://www.Artfiles.de
Hosterplus.de
Bekommen Sie Speicherplatz (Webspace), Domains und...
https://www.Hosterplus.de
 
 
 

Implementierung des Bubblesort-Algorithmus in PHP: Ein Schritt-für-Schritt-Tutorial

Sie befinden sich: Home > Php Tutorial > Bubblesort in PHP

Bubblesort in PHP


Eintrag am:  31.10.2011
Hits / Besucher:  29111
Sprache:  Deutsch
Kategorie:  Einsteiger Tutorials...
Tutorial Art:  eigenes
Eingetragen von   schubertmedia schubertmedia
 
Beschreibung

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.

Flussdiagramm des Bubblesort-Algorithmus. Der Ablauf beginnt mit dem Vergleich benachbarter Elemente. Wenn das erste Element größer ist, werden die Elemente getauscht. Anschließend wird der nächste Vergleich durchgeführt. Dieser Prozess wird fortgesetzt, bis alle Elemente sortiert sind.

 

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.

Diagramm, das Anwendungen des Bubblesort-Algorithmus zeigt. Es gibt drei Hauptanwendungsbereiche: Adressbuch sortieren (links), Anzeigen sortieren (Mitte) und Namen sortieren (rechts). Jede Anwendung ist in einem farblich abgesetzten Block dargestellt.

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 &copy; 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.

 

Tags:

 

Artikel hinzufügen bei: