<?php
// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass
function bubbleSort(array $items): array {
$len = count($items);
for ($end = $len; $end > 1; $end--) {
$swapped = false;
for ($j = 1; $j < $end; $j++) {
if ($items[$j] < $items[$j - 1]) {
$tmp = $items[$j];
$items[$j] = $items[$j - 1];
$items[$j - 1] = $tmp;
$swapped = true;
}
}
if (!$swapped) {
break;
}
}
return $items;
}
$items = [ 4, 1, 5, 3, 2 ];
$sortItems = bubbleSort($items);
// sortItems is {1, 2, 3, 4, 5}
print_r($sortItems);
// *** simplified speed test ***
$items = [];
for ($i = 0; $i < 200; $i++) {
$items[$i] = 199 - $i;
}
$count = 10000;
$start = microtime(true);
for ($i = 0; $i < $count; $i++)
bubbleSort($items);
$milliseconds = round((microtime(true) - $start) * 1000);
echo $milliseconds . " milliseconds";
// about 3660 milliseconds