You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
60 lines
1.7 KiB
PHP
60 lines
1.7 KiB
PHP
<?php
|
|
|
|
//license under the MIT https://goo.gl/JNRTRM
|
|
function bucket_sort($my_array) {
|
|
$n = sizeof($my_array);
|
|
$buckets = array();
|
|
// Initialize the buckets.
|
|
for ($i = 0; $i < $n; $i++) {
|
|
$buckets[$i] = array();
|
|
}
|
|
// Put each element into matched bucket.
|
|
foreach ($my_array as $el) {
|
|
array_push($buckets[ceil($el/10)], $el);
|
|
}
|
|
// Sort elements in each bucket using insertion sort.
|
|
$j = 0;
|
|
for ($i = 0; $i < $n; $i++)
|
|
{
|
|
// sort only non-empty bucket
|
|
if (!empty($buckets[$i])) {
|
|
insertion_sort($buckets[$i]);
|
|
// Move sorted elements in the bucket into original array.
|
|
foreach ($buckets[$i] as $el) {
|
|
$my_array[$j++] = $el;
|
|
}
|
|
}
|
|
}
|
|
return $my_array;
|
|
}
|
|
|
|
function insertion_sort($my_array, $fn = 'comparison_function') {
|
|
if (!is_array($my_array) || !is_callable($fn)) return;
|
|
for ($i = 1; $i < sizeof($my_array); $i++) {
|
|
$key = $my_array[$i];
|
|
// This will be $a in comparison function.
|
|
// $key will be the right side element that will be
|
|
// compared against the left sorted elements. For
|
|
// min to max sort, $key should be higher than
|
|
// $elements[0] to $elements[$j]
|
|
$j = $i - 1; // this will be in $b in comparison function
|
|
while ( $j >= 0 && $fn($key, $my_array[$j]) ) {
|
|
$my_array[$j + 1] = $my_array[$j];
|
|
$j = $j - 1; // shift right
|
|
}
|
|
$my_array[$j + 1] = $key;
|
|
}
|
|
}
|
|
|
|
//Following function used to compare each element.
|
|
function comparison_function($a, $b) {
|
|
return $a < $b;
|
|
}
|
|
|
|
$test_array = array(3, 0, 2, 5, -1, 4, 1);
|
|
echo "Original Array :\n";
|
|
echo implode(', ',$test_array );
|
|
echo "\nSorted Array :\n";
|
|
echo implode(', ',bucket_sort($test_array)). PHP_EOL;
|
|
|
|
?>
|