# Bucket sort (Python)

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>>=defbucketSort(arr): initialize counters count amount of each array-number rearrange order of arrayreturnarr

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>>=forvalueinarr: 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 = []fornr, amountinenumerate(count): arr.extend([nr] * amount)

## [edit] Putting it together

To check the bucket sort, we output the data:

<<output the array>>=forvalinarr:

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

Download code |