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

Założenie: Napiszemy funkcję w PHP, która posortuje tablicę liczb całkowitych za pomocą algorytmu sortowania przez scalanie (Merge Sort).

Krok po kroku:

1. Definicja funkcji `mergeSort`: Funkcja ta rekurencyjnie dzieli tablicę na mniejsze podtablice, aż do uzyskania podtablic jednoelementowych (które są już posortowane). Następnie scalamy te podtablice w posortowane tablice większe.

function mergeSort(array $arr): array {
  if (count($arr) <= 1) {
    return $arr;
  }

  $mid = floor(count($arr) / 2);
  $left = array_slice($arr, 0, $mid);
  $right = array_slice($arr, $mid);

  $left = mergeSort($left);
  $right = mergeSort($right);

  return merge($left, $right);
}
				

2. Funkcja `merge`: Ta funkcja scala dwie posortowane podtablice w jedną posortowaną tablicę.

function merge(array $left, array $right): array {
  $result = [];
  $i = $j = 0;

  while ($i < count($left) && $j < count($right)) {
    if ($left[$i] <= $right[$j]) {
      $result[] = $left[$i++];
    } else {
      $result[] = $right[$j++];
    }
  }

  return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}
				

3. Użycie funkcji `mergeSort`: Tworzymy przykładową tablicę i sortujemy ją za pomocą napisanej funkcji.

$numbers = [5, 2, 8, 1, 9, 4, 7, 3, 6];
$sortedNumbers = mergeSort($numbers);
print_r($sortedNumbers); // Wyświetli posortowaną tablicę
				

Algorytm sortowania przez scalanie ma złożoność czasową O(n log n) w najlepszym, średnim i najgorszym przypadku, co czyni go efektywnym algorytmem sortowania dla większych zbiorów danych.

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