Page 264 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 12: Sorting

BUCKET_SORT (A) Notes

1. n ← length [A]
2. For i = 1 to n do

3. Insert A[i] into list B[nA[i]]
4. For i = 0 to n-1 do
5. Sort list B with Insertion sort
6. Concatenate the lists B[0], B[1], . . B[n-1] together in order.

Example: Given input array A[1..10]. The array B[0..9] of sorted lists or buckets after line 5.
Bucket i holds values in the interval [i/10, (i +1)/10]. The sorted output consists of a concatenation

in order of the lists first B[0] then B[1] then B[2] ... and the last one is B[9].
A B
1 .78 0
2 .17 1 .12 .17
3 .39 2 .21 .23 .26
4 .26 3 .39
5 .72 4
6 .94 5
7 .21 6 .68
8 .12 7 .72 .78
9 .23 8
10 .68 9 .94

Analysis

All lines except line 5 take O(n) time in the worst case. We can see inspection that total time to
examine all buckets in line 5 is O(n-1) i.e., O(n).
The only interesting part of the analysis is the time taken by Insertion sort in line 5. Let n be the
i
random variable denoting the number of elements in the bucket B[i]. Since the expected time to
2
sort by INSERTION_SORT is O(n ), the expected time to sort the elements in bucket B[i] is
2
E[O( n )] = O(E[ n ]]
2
i i
Therefore, the total expected time to sort all elements in all buckets is
n-1 ∑ O(E[ n ]) = O ∑ (E[ n ]) ...(1)
2
n-1
2
i=0 i i=0 i
In order to evaluate this summation, we must determine the distribution of each random variable
n.
We have n elements and n buckets. The probability that a given element falls in a bucket B[i] is
1/n i.e., Probability = p = 1/n.

Note This problem is the same as that of “Balls-and-Bin” problem.

LOVELY PROFESSIONAL UNIVERSITY 259