Bucket sort

sorting Algorithm

1. Bucket Sort Design and Analysis Algorithm

2. Bucket Sort 93 42 69 90 52 51 22 29 Array A Array B 1 2 3 4 5 6 7 8 9 42 52 51 69 93 90 Now we will sort each bucket using insertion sort 22 29

3. 1 2 3 4 5 6 7 8 9 42 51 52 69 22 29 90 93 22 29 42 51 52 69 90 93 [0] [ 1] [ 2] [ 3] [4] [ 5] [ 6] [ 7] After sorting each bucket using insertion sort Sorted Array

4. Time complexity n=length[A] 1 time f or i=1 to n n times do insert A[i] into bucket B[n A[i]] O(n) f or i=0 to n-1 n times do sort bucket B[i] with insertion sort ∑O(n^2) Concatenate bucket O(n)

5. Best Case In the best case every element belongs to different buckets so the complexity is O( n+k ) Where n=number of elements and k is the number of buckets

6. Average Case In average case running time of bucket sort is: T(n)= Θ (n)+∑O(n^2) So the average c omplexity is O( n+k )

7. Worst Case In worst case complexity is O(n^2), as every element belongs to one bucket so we have to use insertion sort n elements. Instead of insertion sort we could merge or heap sort because their worst case running time is O(n log n). But we use insertion sort because we expect the buckets to be small and insertion sort works much faster for small array.