B. szybki PHP - bubble sort

Napiszemy algorytm bubble sort w języku PHP. Jest to algorytm in-place, a zatem będziemy musieli przyjąć zmienną zawierającą tablicę jako referencję. Do dzieła.

Pierwsza rzecz – nasza funkcja przyjmuje tablicę jako referencję, aby można ją było modyfikować in-place:

function bubbleSort(&$a)
{
  (...)
}

Druga rzecz – pętla zewnętrzna, która idzie od indeksu ostatniego do indeksu 1:

function bubbleSort(&$a)
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    (...)
  }
}

Dalej – pętla wewnętrzna idąca od indeksu 0 do aktualnego końca wskazywanego przez pętlę zewnętrzną:

function bubbleSort(&$a)
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    for ($j = 0; $j < $i; $j++) {
      (...)
    }
  }
}

Teraz podmianka zawsze wyrzucająca największy element na koniec:

function bubbleSort(&$a)
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    for ($j = 0; $j < $i; $j++) {
      if ($a[$j] > $a[$j + 1]) { 
        $temp = $a[$j];
        $a[$j] = $a[$j+1];
        $a[$j+1] = $temp;
      }
    }
  }
}

Teraz jeszcze optymalizacja – jeżeli nie było żadnej podmianki pętli wewnętrznej, to lista jest już posortowana:

function bubbleSort(&$a)
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    $swap = false;
    for ($j = 0; $j < $i; $j++) {
      if ($a[$j] > $a[$j + 1]) { 
        $temp = $a[$j];
        $a[$j] = $a[$j+1];
        $a[$j+1] = $temp;
        $swap = true;
      }
    }
    if (!$swap) break;
  }
}

Przykład użycia:

$bs = [5, 2, 8, 9, 1];
bubbleSort($bs);
print_r($bs);

Przykład z internetu, gdzie robimy „niby bubble sort”:

function bubbleSortOptimized(array $a): array
{
  for ($i = count($a) - 1; $i > 0; $i--) {
    $swap = false;
    for ($j = 0; $j < $i; $j++) {
      if ($a[$j] > $a[$j + 1]) { 
        $temp = $a[$j];
        $a[$j] = $a[$j+1];
        $a[$j+1] = $temp;
        $swap = true;
      }
    }
    if (!$swap) break;
  }
  return $a;
}
//$bs = [5, 2, 8, 9, 1];
//$outcome = bubbleSort($bs);
//print_r($outcome);

Niby, ponieważ ten przykład zwraca nową tablicę, oryginalna nie zostaje zmieniona. Bubble sort działa in-place i ma zmieniać przekazaną tablicę, nie zwracać inną.

Aby to osiągnąć – przekazujemy zmienną przez referencję.

B. szybki PHP – bubble sort