The third linear time sorting is Bucket Sort.
Bucket sorting, also known as bin sorting, is a method of sorting that divides input numbers into different buckets.
.
Bucket Sort is actually a Counting Sort
When the buckets have a size of 1, bucket sort turns into the counting sort method of sorting, which is where bucket sort got its start.
Sorting by count is simply taking each number out of its original array and returning it to its final resting place. The identical process is carried out in a bucket sort, except many numbers are sorted simultaneously.
One bucket can hold as many numbers as in the input. The sorting within a bucket is done by either using other sorting algorithms (like insertion Sort) or by the nested bucket sort.
Radix sort is like the cousin of counting sort, sharing the idea of sorting based on digits or keys.
Characteristics of Bucket Sort
- It is a comparison-based sorting.
- This sort is stable if underlying sort is stable.
- It is a distribution sorting method.
- It is fast like counting and radix sort.
Working
Input is { .79, .13, .16, .64, .39, .20, .89, .53, .71, .42}.
So, n = 10
- We have to sort an input array, which is 10 numbers long.
- Make equal sized buckets in the interval [0,1) and then distribute the input array numbers to buckets.
- If a bucket has two or more input number, then sort the numbers using insertion sort. This sort can quickly sort the array with less numbers, that’s why insertion sort is in demand.
- Now we write the output in increasing order of buckets. First, we choose bucket 0, then we choose bucket 1, then bucket 2, and so on. If a bucket has two or more numbers, then we write it as the output of the insertion sort.
- Enter the input array
- Create 10 buckets from 0 to 9
- Enter the input number array[i]*10 into relative bucket.
- If a bucket has two or more numbers, then sort it using insertion sort.
- Write the sorted output from bucket 0 to bucket 9.
Â
Source Code of Bucket Sort
// COMPUTER GEEK – compgeek.co.in
// Write a program of Bucket Sort
#include <stdio.h>
// Function to perform insertion sort
void insertionSort(int array[], int n) {
   int i, key, j;
   for (i = 1; i < n; i++) {
       key = array[i];
       j = i – 1;
       // Move elements of array[0..i-1], that are greater than key,
       // to one position ahead of their current position
       while (j >= 0 && array[j] > key) {
           array[j + 1] = array[j];
           j = j – 1;
       }
       array[j + 1] = key;
   }
}
// Function to perform bucket sort
void bucketSort(int array[], int n) {
   // Create 10 buckets
   int buckets[10][10] = {0};
   int bucket_count[10] = {0};
   // Place elements into buckets
   for (int i = 0; i < n; i++) {
       int bucket_index = array[i] / 10;
       buckets[bucket_index][bucket_count[bucket_index]] = array[i];
       bucket_count[bucket_index]++;
   }
   // Sort each bucket using insertion sort
   for (int i = 0; i < 10; i++) {
       if (bucket_count[i] > 1) {
           insertionSort(buckets[i], bucket_count[i]);
       }
   }
   // Write the sorted output from buckets
   printf(“Sorted array: “);
   for (int i = 0; i < 10; i++) {
       for (int j = 0; j < bucket_count[i]; j++) {
           printf(“%d “, buckets[i][j]);
       }
   }
}
int main() {
   int array[100], size;
   // Input array declaration
   printf(“Enter the size of the array: “);
   scanf(“%d”, &size);
   // Input array initialization
   printf(“Enter the %d items of the array: “, size);
   for (int i = 0; i < size; i++) {
       scanf(“%d”, &array[i]);
   }
   // Perform bucket sort
   bucketSort(array, size);
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program of Bucket Sort
#include <iostream>
#include <vector>
using namespace std;
// Function to perform insertion sort
void insertionSort(vector<int>& array) {
   int n = array.size();
   for (int i = 1; i < n; i++) {
       int key = array[i];
       int j = i – 1;
       // Move elements of array[0..i-1], that are greater than key,
       // to one position ahead of their current position
       while (j >= 0 && array[j] > key) {
           array[j + 1] = array[j];
           j = j – 1;
       }
       array[j + 1] = key;
   }
}
// Function to perform bucket sort
void bucketSort(vector<int>& array) {
   // Create 10 buckets
   vector<vector<int>> buckets(10);
   vector<int> bucketCount(10, 0);
   // Place elements into buckets
   for (int i = 0; i < array.size(); i++) {
       int bucketIndex = array[i] / 10;
       buckets[bucketIndex].push_back(array[i]);
       bucketCount[bucketIndex]++;
   }
   // Sort each bucket using insertion sort
   for (int i = 0; i < 10; i++) {
       if (bucketCount[i] > 1) {
           insertionSort(buckets[i]);
       }
   }
   // Write the sorted output from buckets
   cout << “Sorted array: “;
   for (int i = 0; i < 10; i++) {
       for (int j = 0; j < bucketCount[i]; j++) {
           cout << buckets[i][j] << ” “;
       }
   }
}
int main() {
   vector<int> array;
   int size, num;
   // Input array declaration
   cout << “Enter the size of the array: “;
   cin >> size;
   // Input array initialization
   cout << “Enter the ” << size << ” items of the array: “;
   for (int i = 0; i < size; i++) {
       cin >> num;
       array.push_back(num);
   }
   // Perform bucket sort
   bucketSort(array);
   return 0;
}
// COMPUTER GEEK – compgeek.co.in
// Write a program of Bucket Sort
import java.util.ArrayList;
import java.util.Scanner;
public class BucketSort {
   // Function to perform insertion sort
   public static void insertionSort(ArrayList<Integer> array) {
       int n = array.size();
       for (int i = 1; i < n; i++) {
           int key = array.get(i);
           int j = i – 1;
           // Move elements of array[0..i-1], that are greater than key,
           // to one position ahead of their current position
           while (j >= 0 && array.get(j) > key) {
               array.set(j + 1, array.get(j));
               j = j – 1;
           }
           array.set(j + 1, key);
       }
   }
   // Function to perform bucket sort
   public static void bucketSort(ArrayList<Integer> array) {
       // Create 10 buckets
       ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
       for (int i = 0; i < 10; i++) {
           buckets.add(new ArrayList<>());
       }
       ArrayList<Integer> bucketCount = new ArrayList<>();
       for (int i = 0; i < 10; i++) {
           bucketCount.add(0);
       }
       // Place elements into buckets
       for (int i = 0; i < array.size(); i++) {
           int bucketIndex = array.get(i) / 10;
           buckets.get(bucketIndex).add(array.get(i));
           bucketCount.set(bucketIndex, bucketCount.get(bucketIndex) + 1);
       }
       // Sort each bucket using insertion sort
       for (int i = 0; i < 10; i++) {
           if (bucketCount.get(i) > 1) {
               insertionSort(buckets.get(i));
           }
       }
       // Write the sorted output from buckets
       System.out.print(“Sorted array: “);
       for (int i = 0; i < 10; i++) {
           for (int j = 0; j < bucketCount.get(i); j++) {
               System.out.print(buckets.get(i).get(j) + ” “);
           }
       }
   }
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       ArrayList<Integer> array = new ArrayList<>();
       int size;
       // Input array declaration
       System.out.print(“Enter the size of the array: “);
       size = scanner.nextInt();
       // Input array initialization
       System.out.print(“Enter the ” + size + ” items of the array: “);
       for (int i = 0; i < size; i++) {
           array.add(scanner.nextInt());
       }
       // Perform bucket sort
       bucketSort(array);
       scanner.close();
   }
}
# COMPUTER GEEK – compgeek.co.in
# Write a program of Bucket Sort
Â
def insertion_sort(array):
   for i in range(1, len(array)):
       key = array[i]
       j = i – 1
       while j >= 0 and array[j] > key:
           array[j + 1] = array[j]
           j -= 1
       array[j + 1] = key
Â
def bucket_sort(array):
   buckets = [[] for _ in range(10)]
   bucket_count = [0] * 10
Â
   # Place elements into buckets
   for num in array:
       bucket_index = num // 10
       buckets[bucket_index].append(num)
       bucket_count[bucket_index] += 1
Â
   # Sort each non-empty bucket using insertion sort
   for i in range(10):
       if bucket_count[i] > 1:
           insertion_sort(buckets[i])
Â
   # Write the sorted output from buckets
   sorted_array = []
   for i in range(10):
       for num in buckets[i]:
           sorted_array.append(num)
   return sorted_array
Â
def main():
   array = []
   size = int(input(“Enter the size of the array: “))
   print(“Enter the”, size, “items of the array: “)
   for _ in range(size):
       array.append(int(input()))
   sorted_array = bucket_sort(array)
   print(“Sorted array:”, sorted_array)
if __name__ == “__main__”:
   main()
Time & Space complexity of Bucket Sort
In best-case, time complexity is O(n+k).
O(n) is the complexity of creating buckets, and O(k) is the complexity of sorting bucket elements using insertion sort with linear time complexity in the best situation.
If all the buckets have only zero or one element, and if all the bucket’s elements are already sorted, then that is the best case scenario.
In average-case, time complexity is O(n+k).
In worst-case, time complexity is O(n2).
Worst-case occurs when all the elements go into last bucket and they are reverse sorted.
The space complexity is O(n*k)
because n buckets are there in the bucket sort and k memory elements to store all the elements in one bucket.
Advantage of bucket sort
- It is a linear sort.
- Comparisons are low.
- The sort is stable if underlying sort is stable.
- Floating point values get sorted easily.
Disadvantage of bucket sort
- Space complexity is very high O(n*k).
- Not useful for the large array.
- Not in-place algorithm.
Test Yourself
Q1- How does bucket sort work, and what is its main principle for sorting elements?
Bucket sort divides the input numbers into different buckets based on their values.Â
Each bucket can hold a range of numbers, and the elements are distributed to their corresponding buckets.Â
If a bucket contains multiple elements, they can be sorted using an auxiliary sorting algorithm, such as insertion sort.Â
After sorting each bucket, the elements are concatenated back to obtain the sorted output.Â
The main principle behind bucket sort is to distribute elements into appropriate buckets based on their values, which allows for efficient sorting within each bucket.
Q2- Explain the process of choosing the number of buckets in bucket sort and how it can impact the sorting performance.
The number of buckets in bucket sort can be chosen based on the characteristics of the input data.Â
Ideally, the number of buckets should be proportional to the range of input values to ensure that elements are evenly distributed among buckets.Â
Too few buckets might result in some buckets being heavily loaded with elements, leading to less efficient sorting within those buckets.Â
On the other hand, too many buckets can increase overhead and may not be practical for certain data sets.Â
Choosing an appropriate number of buckets can optimize the sorting performance of bucket sort.
Q3- Is bucket sort a comparison-based sorting algorithm? Explain why or why not.
No, bucket sort is not a comparison-based sorting algorithm. Bucket sort uses a different approach by dividing elements into buckets based on their values rather than comparing elements to determine their order.
But, bucket sort uses insertion sort in each bucket, and yes, insertion sort will compare between numbers.
But in bucket sort comparison is not used at all.
Q4- How does the stability of bucket sort depend on the underlying sorting algorithm used within the buckets?
The stability of bucket sort depends on the stability of the underlying sorting algorithm used within the buckets. If the auxiliary sorting algorithm is stable (i.e., it preserves the relative order of equal elements), then bucket sort will also be stable.Â
This is because bucket sort only rearranges elements within each bucket and does not alter the order of elements with equal values.Â
On the other hand, if the underlying sorting algorithm is not stable, bucket sort may lose the stability property, leading to a non-stable sorting result.
Q5- Describe the time complexity of bucket sort in the best-case scenario and the conditions required for this scenario.
In the best-case scenario, the time complexity of bucket sort is O(n + k), where n is the number of elements in the input array, and k is the number of buckets.Â
This occurs when all the elements are uniformly distributed among the buckets, with each bucket containing only one or zero element.Â
In such a situation, the overhead of creating buckets and sorting within each bucket is minimal, means there is no insertion sort in the buckets, resulting in linear time complexity.
Q6- Discuss the space complexity of bucket sort and explain why it may not be suitable for large arrays.
The space complexity of bucket sort is O(n * k), where n is the number of elements in the input array, and k is the number of buckets.Â
Each bucket requires memory to store its elements, and for a large number of buckets or elements, the space requirements can become significant.Â
This makes bucket sort less suitable for large arrays or datasets with a wide range of input values, as it may consume a considerable amount of memory.
Q7- How does bucket sort handle floating-point values during sorting?
Bucket sort can handle floating-point values by mapping the range of input values to the range of bucket indices. The decimal portion of each floating-point value is used to determine which bucket the element belongs to.Â
By dividing the interval [0, 1) into equal-sized buckets, floating-point values can be efficiently distributed among the buckets. This approach allows bucket sort to sort floating-point values with ease.
Q8- Under what conditions does bucket sort perform at its worst, and what contributes to the worst-case time complexity?
The worst-case time complexity of bucket sort occurs when all elements are placed in a single bucket, resulting in O(n^2) time complexity.Â
This situation arises when the input data is heavily skewed, and all elements fall within a narrow range.
In such cases, sorting within the bucket using an auxiliary algorithm, such as insertion sort, becomes inefficient due to the large number of elements to sort.
Q9- Discuss the advantages of bucket sort compared to other sorting algorithms.
Bucket sort has several advantages, including its linear time complexity in the best-case scenario, low number of comparisons, and efficient handling of floating-point values.Â
It is a stable sorting algorithm if the underlying sort is stable, preserving the relative order of equal elements.Â
It is well-suited for sorting elements with a uniform distribution, making it useful for certain data sets.
Q10- What are the main disadvantages of bucket sort, and when might other sorting algorithms be preferred over bucket sort?
One disadvantage of bucket sort is that it can require a lot of memory, especially when dealing with a large number of elements or a wide range of values. Each bucket needs space to store its elements, and if the elements are not evenly distributed among the buckets, some buckets may end up with many elements, leading to increased memory usage.
Additionally, bucket sort may not perform well when the input data is heavily skewed, meaning that a large number of elements fall into a small range of values. In such cases, most elements would end up in a single bucket, and the sorting within that bucket may become inefficient, resulting in slower performance compared to other sorting algorithms.
Q11- Bucket sort is based on which principle for sorting elements?
Comparisons between elements
Distribution into buckets based on values
Rearrangement of elements in a single array
Random swapping of elements
Ans – (2)
Explanation – Bucket sort divides input elements into different buckets based on their values for sorting.
Q12- What contributes to the high space complexity of bucket sort?
Number of elements in the input array
Number of iterations required to sort the elements
Number of comparisons between elements
Number of buckets and memory elements required
Ans – (4)
Explanation – The space complexity of bucket sort is influenced by the number of buckets and the memory elements needed to store the elements in each bucket.
Q13- Bucket sort is suitable for sorting:
Large arrays with skewed distributions
Large arrays with uniformly distributed elements
Small arrays with uniformly distributed elements
Small arrays with sorted elements
Ans – (2)
Explanation – Bucket sort performs well when elements are evenly distributed among the buckets.
Q14- What are the main disadvantages of bucket sort?
High space complexity and sensitivity to skewed distributions
Inefficiency in handling floating-point values and large arrays
Unstable sorting and excessive comparisons between elements
Dependency on the range of input values and the number of buckets
Ans – (1)
Explanation – Bucket sort has a high space complexity and may perform poorly when elements are heavily skewed into a single bucket.
