Algorithms in PHP

binary_search.php

<?php

function binary_search(array $items, $lookingFor) {
  $min = 0;
  $max = count($items);

  while ($min <= $max) {
    $middle = $min + intval(floor($max - $min) / 2);

    if ($items[$middle] === $lookingFor) {
      return $middle;
    }

    if ($middle === $min || $middle === $max) {
      break;
    }

    if ($items[$middle] < $lookingFor) {
      $min = $middle;
    } else {
      $max = $middle;
    }
  }

  return -1;
}

binary_search([4, 8, 15, 16, 23, 42], 3);

bubble_sort.php

<?php

function bubble_sort($items)
{
  do {
    $again = false;

    for ($i = 0; $i < count($items); $i++) {
      $currentValue = $items[$i];
      $nextValue = $items[$i + 1] ?? INF;

      if ($nextValue < $currentValue) {
        $items[$i] = $nextValue;
        $items[$i + 1] = $currentValue;
        $again = true;
      }
    }
  } while ($again);
  
  return $items;
}

$items = [23, 4, 42, 15, 16, 8];
bubble_sort($items);

dfs-and-bfs.php

<?php

class Node
{
  public function __construct(
    public int $value,
    public ?Node $left = null,
    public ?Node $right = null
  ) {}
}

class DFS
{
  public function run(Node $root)
  {
    $stack = [$root];

    while (count($stack) > 0) {
      $current = array_pop($stack);

      if ($current->right) {
        array_push($stack, $current->right);
      }

      if ($current->left) {
        array_push($stack, $current->left);
      }
    }
  }
}

class BFS
{
  public function run(Node $root)
  {
    $queue = [$root];

    while (count($queue) > 0) {
      $current = array_shift($queue);

      if ($current->left) {
        array_push($queue, $current->left);
      }

      if ($current->right) {
        array_push($queue, $current->right);
      }
    }
  }
}

$root = new Node(0);
$root->left = new Node(1);
$root->right = new Node(2);
$root->left->left = new Node(3);
$root->left->right = new Node(4);
$root->right->left = new Node(5);
$root->right->right = new Node(6);

echo "Depth-First Search (DFS):" . PHP_EOL;
(new DFS())->run($root);

echo PHP_EOL;

echo "Breadth-First Search (DFS):" . PHP_EOL;
(new BFS())->run($root);

fibonacci_and_space_time_complexity.php

<?php

function fibonacci_at_slow($position) {
  if ($position < 2) {
    return $position;
  }

  return fibonacci_at_slow($position - 2) + fibonacci_at_slow($position - 1);
}

function fibonacci_at_faster($position) {
  $sequence = [0, 1];

  for ($i = 2; $i <= $position; $i++) {
    $sequence[] = $sequence[$i - 2] + $sequence[$i - 1];
  }

  return $sequence;
}

function fibonacci_at_constant_space($position, $fn = null) {
  $twoFibsAgo = 0;
  $oneFibAgo = 1;
  $currentFib = 0;
  $fn ??= function () {};

  $fn(0);
  $fn(1);

  for ($i = 2; $i <= $position; $i++) {
    $currentFib = $twoFibsAgo + $oneFibAgo;
    $twoFibsAgo = $oneFibAgo;
    $oneFibAgo = $currentFib;

    $fn($currentFib);
  }

  return $currentFib;
}

fibonacci_at_constant_space(10);

merge_sort.php

<?php

function merge(array $left, array $right) {
  $result = [];

  while (count($left) > 0 || count($right) > 0) {
    if (count($left) > 0 && count($right) > 0) {
      if ($left[0] > $right[0]) {
        $result[] = array_shift($right);
      } else {
        $result[] = array_shift($left);
      }
    } elseif (count($left) > 0) {
      $result[] = array_shift($left);
    } else {
      $result[] = array_shift($right);
    }
  }

  return $result;
}

function merge_sort(array $items) {
  if (count($items) === 1) {
    return $items;
  }

  $middle = ceil(count($items) / 2);

  $left = array_slice($items, 0, $middle);
  $right = array_slice($items, $middle);

  return merge(merge_sort($left), merge_sort($right));
}

merge_sort([23, 4, 42, 15, 16, 8, 3]);

quick_sort.php

<?php

function quick_sort(array $items) {
  if (count($items) < 2) return $items;

  $left = $right = [];

  $pivotIndex = count($items) - 1;
  $pivot = $items[$pivotIndex];

  $items = array_values(array_merge(
    array_slice($items, 0, $pivotIndex),
    array_slice($items, $pivotIndex + 1),
  ));

  foreach ($items as $index => $item) {
    if ($item < $pivot) {
      $left[] = $item;
    } else {
      $right[] = $item;
    }
  }

  return array_values(array_merge(
    quick_sort($left),
    [$pivot],
    quick_sort($right),
  ));
}

quick_sort([23, 4, 42, 15, 16, 8, 3]);

selection_sort.php

<?php

class Node
{
  public function __construct(public int $value, public ?Node $left = null, public ?Node $right = null)
  {}
}

class DFS
{
  public function __construct(private Node $root) {}

  public function run()
  {
    $stack = [$this->root];

    while (count($stack) > 0) {
      $current = array_pop($stack);

      if ($current->right) {
        array_push($stack, $current->right);
      }

      if ($current->left) {
        array_push($stack, $current->left);
      }
    }
  }
}

class BFS
{
  public function __construct(private Node $root) {}

  public function run()
  {
    $queue = [$this->root];

    while (count($queue) > 0) {
      $current = array_shift($queue);

      if ($current->left) {
        array_push($queue, $current->left);
      }

      if ($current->right) {
        array_push($queue, $current->right);
      }
    }
  }
}

$root = new Node(0);
$root->left = new Node(1);
$root->right = new Node(2);
$root->left->left = new Node(3);
$root->left->right = new Node(4);
$root->right->left = new Node(5);
$root->right->right = new Node(6);

echo "Depth-First Search (DFS):" . PHP_EOL;
(new DFS($root))->run();

echo PHP_EOL;

echo "Breadth-First Search (DFS):" . PHP_EOL;
(new BFS($root))->run();