Bucket sort (Python)

Jump to: navigation, search
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>>=
def 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 = [0] * len(arr)
```

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

```<<count amount of each array-number>>=
for value in arr:
count[value] += 1
```

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

```<<rearrange order of array>>=
arr = []
for nr, amount in enumerate(count):
arr.extend([nr] * amount)
```

Putting it together

To check the bucket sort, we output the data:

```<<output the array>>=
for val in arr:
print val,
print
```

Putting it all together with a example array.

```<<bucketsort.py>>=
sort function
arr = [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
```