What is Bucket Sort?
GIAN Tutorials
11:10 PM
Bucket Sort Bucket sort is also known as bin sort. It works by distributing the element into the array also called buckets. Buckets are sorted individually by using different sorting algorithm. Complexity of Bucket Sort Algorithm Complexity Space O(1) Worst Case O(n 2 ) Best Case Ω(n+k) Average Case θ(n+k) Algorithm Step 1 START Step 2 Set up an array of initially empty "buckets". Step 3 Scatter: Go over the original array, putting each object in its bucket. Step 4 Sort each non-empty bucket. Step 5 Gather: Visit the buckets in order and put all elements back into the original array. Step 6 STOP Program #include <stdio.h> void Bucket_Sort( int array[], int n) { int i, j; int count[n]; for (i = 0 ; i < n; i++) count[i] = 0 ; for (i = 0 ; i < n; i++) (count[array[i]])++; for (i = 0 , j = 0 ; i < n; i++) for (; count[i] &g
