# Bucket sort (PHP)

### From LiteratePrograms

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