A bucket sort begins with a single-subscripted array of positive integers to be sorted, and a double-subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n-1 where n is the number fo values in the array to be sorted. Each row of the double-subscripted array is refered to as a bucket.
Algorithm works as follows:
1. Each value of the single-subscripted array is placed into a row of the bucket array based
on the value's ones digit. This is called the "distribution pass".
2. Loop through the bucket array row-by-row and copy the values back to the original
array. This is called a "gathering pass".
3. Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.).
Note that the double-subscripted array of the buckets is ten times the size of the integer
array being sorted. This sorting technique provides better performance than a bubble sort, but
requires much more memory.
This version of the bucket sort requires copying all the data back to the original array on
each pass. Another possibility is to create a second double-subscripted bucket array
and repeatedly swap the data between the two bucket arrays.
| Home | Next algorithm |