bucket sort Algorithm
Bucket Sort is a sorting algorithm that works by dividing a given data set into a number of smaller groups called "buckets." These buckets are essentially smaller sorted lists that are later combined to form the final sorted list. The Bucket Sort algorithm is mainly used when the data is uniformly distributed over a specific range, as it takes advantage of this distribution to sort the data efficiently. This algorithm is particularly useful for sorting large data sets or for cases where the data is well distributed, as it can have a linear time complexity under these conditions.
To execute the Bucket Sort algorithm, the first step involves dividing the range of the input data into a predefined number of equally sized buckets. Next, the data is distributed among these buckets based on their values, typically using a hashing function to determine the appropriate bucket for each element. Once the data is allocated to the respective buckets, each bucket is then sorted individually using a different sorting algorithm, such as insertion sort. Finally, the sorted elements from each bucket are concatenated to obtain the complete sorted list. The overall efficiency of the Bucket Sort algorithm relies on the uniform distribution of data across the buckets, as this ensures that the individual sorting of each bucket is a smaller and more manageable task.
DEFAULT_BUCKET_SIZE = 5
def bucket_sort(input, bucket_size = DEFAULT_BUCKET_SIZE)
print 'Array is empty' if input.empty?
array = input.split(' ').map(&:to_i)
bucket_count = ((array.max - array.min) / bucket_size).floor + 1
# create buckets
buckets = []
bucket_count.times { buckets.push [] }
# fill buckets
array.each do |item|
buckets[((item - array.min) / bucket_size).floor].push(item)
end
# sort buckets
buckets.each do |bucket|
bucket.sort!
end
buckets.flatten.join(' ')
end
puts "Enter a list of numbers seprated by space"
list = gets
print bucket_sort(list)
