# Bucket sort (PHP)

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
```