BUCKET
SORT
ALGORITHM
1
What is bucket sort?
is a sorting algorithm that separates the elements into multiple groups said to be
buckets. Elements in bucket sort are first uniformly divided into groups called buckets,
and then they are sorted by any other sorting algorithm. After that, elements are
gathered in a sorted manner.
2
How it works
01 The elements are divided into different buckets.
02 Each bucket is sorted individually.
The sorted buckets are then concatenated to form the sorted
03 output.
3
The basic procedure of performing the bucket sort is given as follows
First, partition the range into a fixed number of buckets
Then, toss every element into its appropriate bucket.
After that, sort each bucket individually by applying a sorting
algorithm.
And at last, concatenate all the sorted buckets.
4
Code:
[Link]
6
1. Finding the Maximum Element
7
PURPOSE: This function scans the array to find the largest number.
How it works:
INITIALIZATION:
max is set to INT_MIN (the smallest possible integer)
to ensure that any number in the array will be larger.
LOOP:
It iterates over each element in the array.
If the current element (array[i]) is greater than max,
it updates max with that value.
RETURN:
After checking all elements,
it returns the maximum value found.
8
2. Bucket Sort Implementation
9
STEPS
1 Find Maximum Element
Calls max_element to determine the maximum value in the
input array.
This value (max) defines the range of possible numbers.
2 Create Buckets
Declares an array bucket of size max+1.
Each index in bucket represents a possible value
from 0 to max.
10
3 Initialize Buckets
The second loop goes through the original array.
For each element array[i],
it increments the corresponding bucket at bucket[array[i]].
4 Populate Buckets
The loop sets every bucket element to 0.
This initialization ensures that each bucket
starts with a count of zero.
RESULT:
The bucket array now holds the frequency (count)
of each number in the input array.
11
5 Merge Buckets Back to the Array
A new index j is initialized to 0 to track
the position in the original array.
The outer loop iterates over all possible numbers from 0 to max.
The inner while loop checks if there are
occurrences of the current number (i) by verifying bucket[i] > 0.
For every occurrence,
it places i in the array at index j and then increments j.
It decrements the count in bucket[i] after each placement.
RESULT:
The original array is overwritten
with the sorted numbers in ascending order.
12
3. The main() Function
13
INPUT:
The program asks the user to enter
the size of the array (num).
It then reads num integers into the array.
DISPLAY BEFORE SORTING:
It prints the unsorted array.
SORTING PROCESS:
Calls Bucket_Sort to sort the array.
DISPLAY AFTER SORTING:
It prints the array after it has been sorted.
14
TRY INPUT THESE
15
SIMULATION
FINDING THE MAXIMUM ELEMENT
max_element is called with the array [20, 5, 1, 3, 10]
PASSES
1 (i = 0):
Element: 20
20 > INT_MIN → update max to 20
2 (i = 1):
Element: 5
5 > 20? False → max remains 20
16
[20, 5, 1, 3, 10]
RESULT:
3 (i = 2): The maximum element is 20.
Element: 1
1 > 20? False → max remains 20
4 (i = 3):
Element: 3
3 > 20? False → max remains 20
5 (i = 4):
Element: 10
10 > 20? False → max remains 20
17
SIMULATION
COUNTING OCCURENCES
[20, 5, 1, 3, 10]
PASSES
1 (i = 0):
Element: 20
Increment bucket[20]: 0 → 1
18
[20, 5, 1, 3, 10]
2 (i = 1): 5 (i = 4):
Element: 5 Element: 10
Increment bucket[5]: 0 → 1 Increment bucket[10]: 0 → 1
3 (i = 2):
Element: 1
Increment bucket[1]: 0 → 1
4 (i = 3):
Element: 3
Increment bucket[3]: 0 → 1
19
[20, 5, 1, 3, 10]
2 (i = 1): 5 (i = 4):
Element: 5 Element: 10
Increment bucket[5]: 0 → 1 Increment bucket[10]: 0 → 1
3 (i = 2):
Element: 1
Increment bucket[1]: 0 → 1
4 (i = 3):
Element: 3
Increment bucket[3]: 0 → 1
20
Bucket Array After Counting:
13 0
Bucket Index Frequency 6 0
14 0
0 0 7 0
15 0
1 1 8 0
16 0
2 0 9 0
17 0
3 1 10 1
18 0
4 0 11 0
19 0
5 1 12 0
20 1
21
SIMULATION
RECONSTRUCTING THE SORTED ARRAY
22
PASSES
1 (i = 0): 4 (i = 3):
bucket[0] is 0 → no action. bucket[3] is 1:
2 (i = 1): Set array[1] = 3
bucket[1] is 1: Decrement bucket[3]: 1 → 0
Set array[0] = 1 Now, j becomes 2.
Decrement bucket[1]: 1 → 0 5 (i = 4):
Now, j becomes 1. bucket[4] is 0 → no action.
3 (i = 2):
bucket[2] is 0 → no action.
23
6 (i = 5): 12-20
bucket[5] is 1: (i = 11) - (i = 19)
Buckets are 0 → no action.
Set array[2] = 5
Decrement bucket[5]: 1 → 0 21 (i = 20):
Now, j becomes 3. bucket[20] is 1:
7-10 Set array[4] = 20
(i = 6) - (i = 9)
Decrement bucket[20]: 1 → 0
Buckets are 0 → no action.
Now, j becomes 5.
11 (i = 10):
bucket[10] is 1: Decrement bucket[10]: 1 → 0
Set array[3] = 10 Now, j becomes 4.
24
22 (i = 21):
21 <= 20, False
END PROGRAM
THE ARRAY NOW BECOMES:
[1, 3, 5, 10, 20]
OUTPUT:
25