## Bucket Sort

Bucket Sort – bucket sorting. The algorithm is similar to sorting by counting, with the difference that the numbers are collected into “buckets”-ranges, then the buckets are sorted using any other, sufficiently productive, sorting algorithm, and the final chord is the expansion of the “buckets” one by one, resulting in a sorted list.

The time complexity of the algorithm is O(nk). The algorithm runs in linear time for data that obeys a uniform distribution. To put it simply, the elements must be in a certain range, without “splashes”, for example, numbers from 0.0 to 1.0. If among such numbers there are 4 or 999, then such a series, according to the laws of the yard, is no longer considered “even”.

Implementation example in Julia:

``````function bucketSort(numbers, bucketsCount)
buckets = Vector{Vector{Int}}()

for i in 0:bucketsCount - 1
bucket = Vector{Int}()
push!(buckets, bucket)
end

maxNumber = maximum(numbers)

for i in 0:length(numbers) - 1
bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
push!(buckets[bucketIndex], numbers[1 + i])
end

for i in 0:length(buckets) - 1
bucketIndex = 1 + i
buckets[bucketIndex] = sort(buckets[bucketIndex])
end

flat = [(buckets...)...]
print(flat, "\n")

end

numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)``````

The performance of the algorithm is also affected by the number of buckets, for more numbers it is better to take a larger number of buckets (Algorithms in a nutshell by George T. Heineman)

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort