SORTING - Introduction to Java Programming: Comprehensive Version - page 882

// Now move the elements from the buckets back to list
int k = 0 ; // k is an index for list
for ( int i = 0 ; i < bucket.length; i++) {
if (bucket[i] != null ) {
for ( int j = 0 ; j < bucket[i].size(); j++)
list[k++] = bucket[i].get(j);
}
}
}

Clearly, it takes O ( n t ) space, where n is the list size.

Note that if t is too large, using the bucket sort is not desirable. Instead, you can use a radix
sort. The radix sort is based on the bucket sort, but a radix sort uses only ten buckets.
It is worthwhile to note that a bucket sort is stable , meaning that if two elements in the
original list have the same key value, their order is not changed in the sorted list. That is, if
element e 1 and element e 2 have the same key and e 1 precedes e 2 in the original list, e 1 still
precedes e 2 in the sorted list.
Assume that the keys are positive integers. The idea for the radix sort is to divide the keys
into subgroups based on their radix positions. It applies a bucket sort repeatedly for the key
values on radix positions, starting from the least-significant position.
Consider sorting the elements with the following keys:
331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9

+ t ) time to sort the list and uses O ( n +

stable

radix sort

radix sort on Companion
Website
queue Apply the bucket sort on the last radix position, and the elements are put into the buckets as follows:

230 331

231

343
453

454
34

45
345

59
9

bucket[0] bucket[1] bucket[2] bucket[3] bucket[4] bucket[5] bucket[6] bucket[7] bucket[8] bucket[9]

After being removed from the buckets, the elements are in the following order:
230, 331, 231, 343, 453, 454, 34, 45, 345, 59, 9

Apply the bucket sort on the second-to-last radix position, and the elements are put into the
buckets as follows:

queue

230
331
231
34

343
45
345

453
454
59

9

bucket[0] bucket[1] bucket[2] bucket[3] bucket[4] bucket[5] bucket[6] bucket[7] bucket[8] bucket[9]

After being removed from the buckets, the elements are in the following order:

9, 230, 331, 231, 34, 343, 45, 345, 453, 454, 59

(Note that 9 is 009 .)
Apply the bucket sort on the third-to-last radix position, and the elements are put into the
buckets as follows:

queue

9
34
45
59

230
231

331
343
345

453
454

bucket[1] bucket[2] bucket[3] bucket[4] bucket[5] bucket[6] bucket[7] bucket[8] bucket[9]

bucket[0]