Bucket sort (PHP)

From LiteratePrograms

Other implementations: C | Java | PHP | Python

Bucket sort is possibly the simplest distribution sorting algorithm. The essential requirement is that the size of the array from which the elements to be sorted are drawn is a small, fixed constant, say n.

<<sort function>>=
function bucketSort($arr) {
  initialize counters
  count amount of each array-number
  rearrange order of array
  return $arr;
}

For example, suppose that we are sorting elements drawn from {0, 1, . . ., n-1}. The integers in this set can be of the range 0 until (n-1). Bucket sort uses n counters. These counters first have to be initialized:

<<initialize counters>>=
$count = array_fill(0, count($arr), 0);

To we can determine the amount of each number in the array we want to sort.

<<count amount of each array-number>>=
foreach ($arr as $value) {
  $count[$value]++;
}

After we've determined all needed information about the array we want to sort. The array can be sorted.

<<rearrange order of array>>=
$arr = array();
foreach ($count as $nr => $amount) {
  for ($i=0; $i < $amount;$i++) {
    array_push($arr, $nr);
  }
}

Putting it together

To check the bucket sort, we output the data:

<<output the array>>=
echo implode(" ", $arr), "\n";

Putting it all together with a example array.

<<bucketsort.php>>=
<?php
sort function
$arr = array(1,3,4,6,4,2,9,1,2,9);
output the array
$arr = bucketSort($arr);
output the array
?>

This generates following output:

1 3 4 6 4 2 9 1 2 9 
1 1 2 2 3 4 4 6 9 9