Sortowanie tablic z użyciem algorytmów sortowania – implementacja sortowania stogowego

Założenie: Nauczyć się implementować algorytm sortowania stogowego (Heapsort) w PHP i zrozumieć jego działanie.

Krok po kroku:

1. Tworzenie funkcji budującej kopiec:

function buildHeap(&$arr, $n) {
  for ($i = floor($n / 2) - 1; $i >= 0; $i--) {
    heapify($arr, $n, $i);
  }
}
				

Funkcja ta iteruje przez tablicę od połowy do początku, wywołując funkcję heapify dla każdego elementu, aby upewnić się, że spełnia on warunek kopca.

2. Tworzenie funkcji heapify:

function heapify(&$arr, $n, $i) {
  $largest = $i;
  $l = 2 * $i + 1;
  $r = 2 * $i + 2;

  if ($l < $n && $arr[$l] > $arr[$largest]) {
    $largest = $l;
  }

  if ($r < $n && $arr[$r] > $arr[$largest]) {
    $largest = $r;
  }

  if ($largest != $i) {
    $temp = $arr[$i];
    $arr[$i] = $arr[$largest];
    $arr[$largest] = $temp;
    heapify($arr, $n, $largest);
  }
}
				

Funkcja heapify sprawdza, czy dany węzeł spełnia warunek kopca. Jeśli nie, zamienia go z największym z jego dzieci i rekurencyjnie wywołuje samą siebie.

3. Implementacja sortowania stogowego:

function heapSort(&$arr) {
  $n = count($arr);
  buildHeap($arr, $n);
  for ($i = $n - 1; $i > 0; $i--) {
    $temp = $arr[0];
    $arr[0] = $arr[$i];
    $arr[$i] = $temp;
    heapify($arr, $i, 0);
  }
}

$arr = array(12, 11, 13, 5, 6, 7);
heapSort($arr);
print_r($arr); // Wynik: Array ( [0] => 5 [1] => 6 [2] => 7 [3] => 11 [4] => 12 [5] => 13 )
				

Funkcja heapSort buduje kopiec, a następnie iteracyjnie zamienia korzeń (największy element) z ostatnim elementem i zmniejsza rozmiar kopca. Następnie ponownie tworzy kopiec z mniejszego zbioru.

Ten przykład pokazuje podstawy implementacji algorytmu sortowania stogowego w PHP. Zachęcamy do dalszego zgłębiania tematu i eksperymentowania z różnymi algorytmami sortowania!