BUCKET SORT INTRODUCTION • BUCKET SORT ALGORITHM
DIVIDES THE UNSORTED ARRAY INTO SEVERAL GROUPS WHICH WE CALLED BUCKET.
• EACH BUCKETS IS SORTED BY USING ANY OF THE SUITABLE SORTING ALGORITHMS OR RECURSIVELY APPLYING THE BUCKET ALGORITHM EXAMPLE How bucket sort Algorithm works Suppose the input in the array are Create an array of size = ten, and each block of an array is used as
a bucket for sorting element COMPLEXITY OF
BUCKET SORT Time complexity •
Best Case On + k) •
Worst Case O(n²) •
Average Case O(n) •
Space Complexity O(n + k) where
•
n is the number of elements • k is the number of
buckets BUCKET SORT ALGORITHM It divides the unsorted array into several groups termed buckets. Each buckets sorted by using any of the suitable sorting algorithms or recursively applying the same bucket algorithm.
1. Create an empty array of size n(n empty buckets.
2. Loop through the original array and put each array element in a bucket.
3. Sort each of the nonempty buckets using insertion sort.
4. Visit the buckets in order and put all elements
back into the original array APPLICATION OF BUCKET SORT INC PROGRAMMING This C program sorts elements of an integer array using Bucket sort. OUTPUT
Enter the size of array 5 Enter the 5
Element to be sorted 2, 0, 4, 1, 3 The array of elements before sorting :
2, 0, 4, 1, 3 The array of elements after sorting :
0, 1, 2, 3, 4
