This Python program implements Bucket Sort, a sorting algorithm that divides the input data into buckets and then sorts each bucket individually, typically using another sorting algorithm like insertion sort.
Bucket Sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets, sorting each bucket individually, and then concatenating the sorted buckets to obtain the sorted array.
Problem Statement
Given an array of floating-point numbers, implement Bucket Sort to sort the array in ascending order.
Python Program to Implement Bucket Sort
def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j >= 0 and key < bucket[j]: bucket[j + 1] = bucket[j] j -= 1 bucket[j + 1] = key def bucket_sort(arr): # Determine the number of buckets to use num_buckets = len(arr) # Create empty buckets buckets = [[] for _ in range(num_buckets)] # Distribute elements into buckets for num in arr: index = int(num * num_buckets) buckets[index].append(num) # Sort each bucket using insertion sort for bucket in buckets: insertion_sort(bucket) # Concatenate sorted buckets sorted_array = [] for bucket in buckets: sorted_array.extend(bucket) return sorted_array # Input arr = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51] # Output sorted_arr = bucket_sort(arr) print("Original Array:", arr) print("Sorted Array:", sorted_arr)
How it Works
- Determine the number of buckets to be used. In this example, we’re using the same number of buckets as the length of the input array.
- Create empty buckets.
- Distribute elements from the input array into the buckets based on their value. Each element is multiplied by the number of buckets, and the resulting integer part is used as the index for the bucket.
- Sort each individual bucket using an auxiliary sorting algorithm (in this case, we’re using Insertion Sort).
- Concatenate the sorted buckets to obtain the final sorted array.
Input/Output
![This Python program implements Bucket Sort, a sorting algorithm that divides the input data into buckets and then sorts each bucket individually, typically using another sorting algorithm like insertion sort.](https://developerpublish.com/wp-content/uploads/2023/08/Screenshot-2023-08-30-180635-1024x615.png)