# Bucket sort (Java)

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>>=
public static int[] bucketSort(int[] arr) {
int i, j;
int[] count = new int[arr.length];
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). The elements of an integer array are initialized to 0 when created.

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

```<<count amount of each array-number>>=
for(i = 0; i < arr.length; i++ ) {
count[arr[i]]++;
}
```

After we've determined all needed information about the array we want to sort. The array can be sorted. `j` holds the current position in the array to sort. `i` holds the current position in the counter array,

```<<rearrange order of array>>=
for(i=0,j=0; i < count.length; i++) {
for(; count[i]>0; (count[i])--) {
arr[j++] = i;
}
}
```

## Putting it together

To check the bucket sort, we output the data:

```<<output the array>>=
for(int i = 0; i < arr.length; i++ ) {
System.out.print(arr[i] + " ");
}
System.out.println();
```

Putting it all together with a example array.

```<<Bucketsort.java>>=
import java.util.Arrays;
public class Bucketsort {
sort function
public static void main(String[] args) {
int[] arr = new int[] {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
```