[PHP] Jak wykonać sortowanie bąbelkowe (algorytm Bubble Sort)?

Chcesz wykorzystać do sortowania algorytm BubbleSort, czyli sortowanie metodą bąbelkową.

To bardzo prosty algorytm, który nadaje się do sortowania niewielkich tablic. Polega na przemieszczaniu na koniec tablicy największych wartości, przez co sposób przypomina wypływanie na powierzchnię wody bąbli - stąd wzięła się jego nazwa.

Algorym polega na porównywaniu kolejnych, sąsiadujących elementów. Jeżeli poprzedni jest większy niż aktualny, ich pozycje są zamieniane. Algorytm wykorzystuje dwie pętle for, w których przegląda zawartość tablicy.

<?

$t = array(7, 9, 1, 2, 6, 7, 3);

$n = count($t); // liczba elementów tablicy

for ($i=0;$i<$n-1;$i++) {

for ($j=$n-1;$j>$i;$j--) {

if ($t[$j]<$t[$j-1]) {

list($t[$j],$t[$j-1]) = array($t[$j-1],$t[$j]);

}

}

}

for($i=0;$i<$n;$i++) echo $t[$i],", ";

// wynik: 1, 2, 3, 6, 7, 7, 9,

?>

Wymiana elementów tablicy została wykonana przy pomocy triku z list() i array(), bez potrzeby korzystania ze zmiennej tymczasowej.

Powyższy algorytm jest wzorcowy, jednak w praktyce stosuje się jego modyfikację, która jest nieco szybsza, w przypadku gdy tablica jest wstępnie posortowana (lub jeżeli jest w pełni posortowana).

<?

$t = array(7, 9, 1, 2, 6, 7, 3);

$dalej=true;

$n = count($t); // liczba elementów tablicy

for ($i=0;$i<$n-1 && $dalej;$i++) {

$dalej = false;

for ($j=$n-1;$j>$i;$j--) {

if ($t[$j]<$t[$j-1]) {

list($t[$j],$t[$j-1]) = array($t[$j-1],$t[$j]);

$dalej = true;

}

}

}

for($i=0;$i<$n;$i++) echo $t[$i],", ";

// wynik: 1, 2, 3, 6, 7, 7, 9,

?>

W tym algorytmie zakładamy od razu, że tablica jest posortowana i po wejściu do pętli zmienna $dalej otrzymuje wartość false. Dopiero w momencie, gdy nastąpi zmiana miejsc, nadajemy jej wartość true i dalej sortujemy tablicę. Gdy nie było żadnej zamiany, nie ma sensu dalej przeszukiwać elementów (wszystko jest posortowane) i wychodzimy z pętli.

---