Bucket Sort
Prof. Prateek Vishnoi
September 9, 2024
Bucket Sort
Assumptions
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Each element belongs to (0,1).
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Each element belongs to (0,1).
Bucket Sort
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Each element belongs to (0,1).
Bucket Sort
It divides the [0,1] into n-equal sized subintervals or buckets.
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Each element belongs to (0,1).
Bucket Sort
It divides the [0,1] into n-equal sized subintervals or buckets.
After that it distributes the n input numbers into the buckets.
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Each element belongs to (0,1).
Bucket Sort
It divides the [0,1] into n-equal sized subintervals or buckets.
After that it distributes the n input numbers into the buckets.
Call the insertion sort on each bucket.
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
Assumptions
Input is uniformly independently distributed.
Each element belongs to (0,1).
Bucket Sort
It divides the [0,1] into n-equal sized subintervals or buckets.
After that it distributes the n input numbers into the buckets.
Call the insertion sort on each bucket.
Concatenate each bucket.
Prof. Prateek Vishnoi Bucket Sort
Bucket Sort
[Link] Introduction to Algorithms, Cormen, Leiserson, Rivest
and Stein
Prof. Prateek Vishnoi Bucket Sort
Running Time
Notice that time taken before insertion sort is Θ(n).
Prof. Prateek Vishnoi Bucket Sort
Running Time
Notice that time taken before insertion sort is Θ(n).
Let ni be RV denoting number of elements placed in bucket
B[i].
Prof. Prateek Vishnoi Bucket Sort
Running Time
Notice that time taken before insertion sort is Θ(n).
Let ni be RV denoting number of elements placed in bucket
B[i].
n−1
X
T (n) = Θ(n) + O(ni2 )
i=0
Prof. Prateek Vishnoi Bucket Sort
Running Time
Notice that time taken before insertion sort is Θ(n).
Let ni be RV denoting number of elements placed in bucket
B[i].
n−1
X
T (n) = Θ(n) + O(ni2 )
i=0
We now analyse the average-case running time of bucket sort
by taking the expected value of running time over the input
distribution.
Prof. Prateek Vishnoi Bucket Sort
Continued...
n−1
X
T (n) = Θ(n) + O(ni2 )
i=0
Prof. Prateek Vishnoi Bucket Sort
Continued...
n−1
X
T (n) = Θ(n) + O(ni2 )
i=0
n−1
X
E [T (n)] = Θ(n) + E [O(ni2 )] {By linearity of expectation}
i=0
Prof. Prateek Vishnoi Bucket Sort
Continued...
n−1
X
T (n) = Θ(n) + O(ni2 )
i=0
n−1
X
E [T (n)] = Θ(n) + E [O(ni2 )] {By linearity of expectation}
i=0
n−1
X
E [T (n)] = Θ(n) + O(E [ni2 ])
i=0
Prof. Prateek Vishnoi Bucket Sort
E [ni2 ]??
Prof. Prateek Vishnoi Bucket Sort
E [ni2 ]??
Define Xi,j as indicator RV denoting A[j] falls in bucket i for
buckets i = 0, 1, 2, . . . (n − 1) and j = 1, 2 . . . n
Prof. Prateek Vishnoi Bucket Sort
E [ni2 ]??
Define Xi,j as indicator RV denoting A[j] falls in bucket i for
buckets i = 0, 1, 2, . . . (n − 1) and j = 1, 2 . . . n
n
X
ni = Xi,j
j=1
Prof. Prateek Vishnoi Bucket Sort
E [ni2 ]??
Define Xi,j as indicator RV denoting A[j] falls in bucket i for
buckets i = 0, 1, 2, . . . (n − 1) and j = 1, 2 . . . n
n
X
ni = Xi,j
j=1
P(Xi,j = 1) = 1/n
Prof. Prateek Vishnoi Bucket Sort
Continued...
Prof. Prateek Vishnoi Bucket Sort
Continued...
" n
!2 #
X
E [ni2 ] =E Xi,j
j=1
Prof. Prateek Vishnoi Bucket Sort
Continued...
" n
!2 #
X
E [ni2 ] =E Xi,j
j=1
n
" #
X X X
2
=E Xi,j + Xi,j Xi,k
j=1 1≤j≤n 1≤k≤n
j̸=k
Prof. Prateek Vishnoi Bucket Sort
Continued...
" n
!2 #
X
E [ni2 ] =E Xi,j
j=1
n
" #
X X X
2
=E Xi,j + Xi,j Xi,k
j=1 1≤j≤n 1≤k≤n
j̸=k
n
X X X
2
= E [Xi,j ]+ E [Xi,j Xi,k ]
j=1 1≤j≤n 1≤k≤n
j̸=k
Prof. Prateek Vishnoi Bucket Sort
Continued...
" n
!2 #
X
E [ni2 ] =E Xi,j
j=1
n
" #
X X X
2
=E Xi,j + Xi,j Xi,k
j=1 1≤j≤n 1≤k≤n
j̸=k
n
X X X
2
= E [Xi,j ]+ E [Xi,j Xi,k ]
j=1 1≤j≤n 1≤k≤n
j̸=k
Xi,j and Xi,k are independent. We now calculate,
2 1
E [Xi,j ] = 12 . = 1/n which is also equal toE [Xi,j ]
n
Prof. Prateek Vishnoi Bucket Sort
Continued...
1 1 1
E [ni2 ] = n. + 2.n C2 . .
n n n
1 1
= 1 + n(n − 1). 2 = 2 −
n n
Prof. Prateek Vishnoi Bucket Sort
Continued...
1 1 1
E [ni2 ] = n. + 2.n C2 . .
n n n
1 1
= 1 + n(n − 1). 2 = 2 −
n n
n−1
X
E [T (n)] = Θ(n) + O(E [ni2 ])
i=0
Prof. Prateek Vishnoi Bucket Sort
Continued...
1 1 1
E [ni2 ] = n. + 2.n C2 . .
n n n
1 1
= 1 + n(n − 1). 2 = 2 −
n n
n−1
X
E [T (n)] = Θ(n) + O(E [ni2 ])
i=0
1
E [T (n)] = Θ(n) + n.(2 − ) = Θ(n)
n
Prof. Prateek Vishnoi Bucket Sort
Finally Sorting is SORTED for this course
Last Judgement Question
What will happen if we use Merge Sort in place of Insertion
sort in Bucket Sort ??
Prof. Prateek Vishnoi Bucket Sort
Finally Sorting is SORTED for this course
Last Judgement Question
What will happen if we use Merge Sort in place of Insertion
sort in Bucket Sort ??
Remember, there is no last question, they are countably infinite....
Prof. Prateek Vishnoi Bucket Sort