Illustrate the operation of Bucket sort on the array 12 58 3

Illustrate the operation of Bucket sort on the array:  

12 58 37 64 52 36 99 63 18 9 20 88 47

Solution

################# BUCKET SORT ##########################

12 58 37 64 52 36 99 63 18 9 20 88 47

The goal: sort N numbers, all between 1 to k
The method: Use an array of k queues. Queue j
(for 1 j k) keeps the input numbers whose
value is j

elements of array are between 1 and 99
Thus, creating an array of size 99

here, k = 99
Each queue is denoted as ‘a bucket’

Step 1: scan the list and put the elements in
the queues

bucket 1   => 0
bucket 2   => 0
.
.
bucket 8   => 0
bucket 9   => 9
bucket 10 => 0
bucket 11 => 0
bucket 12 => 12
.
.
bucket 17 => 0
bucket 18 => 18
bucket 19 => 0
bucket 20 => 20
.
.
bucket 35 => 0
bucket 36 => 36
bucket 37 => 37
.
.
bucket 46 => 0
bucket 47 => 47
.
.
bucket 51 => 0
bucket 52 => 52
.
.
bucket 57 => 0
bucket 58 => 58
bucket 59 => 0
bucket 60 => 0
bucket 61 => 0
bucket 62 => 0
bucket 63 => 63
bucket 64 => 64
.
.
bucket 87 => 0
bucket 88 => 88
bucket 89 => 0
.
.

bucket 98 => 0
bucket 99 => 99

Step 2: concatenate the queues
bucket 9   => 9
bucket 12 => 12
bucket 18 => 18
bucket 20 => 20
bucket 36 => 36
bucket 37 => 37
bucket 47 => 47
bucket 52 => 52
bucket 58 => 58
bucket 63 => 63
bucket 64 => 64
bucket 88 => 88
bucket 99 => 99

Step 3: Output the content of the buckets from 1 to k(99)
Sorted buckets
=> 9 12 18 20 36 37 47 52 58 63 64 88 99
Time complexity: O(n+k).