Tag Archives: bucketsort

Classificação por bucket – classificação por buckets. O algoritmo é semelhante à classificação por contagem, com a diferença de que os números são coletados em intervalos de “baldes”, então os baldes são classificados usando qualquer outro algoritmo de classificação suficientemente produtivo, e a etapa final é desdobrar os “baldes” um por um, resultando em uma lista ordenada

.

A complexidade de tempo do algoritmo é O(nk). O algoritmo funciona em tempo linear para dados que obedecem a uma lei de distribuição uniforme. Simplificando, os elementos devem estar em um determinado intervalo, sem “picos”, por exemplo, números de 0,0 a 1,0. Se entre esses números houver 4 ou 999, então, de acordo com as leis do pátio, essa linha não será mais considerada “par”.

Exemplo de implementação em Julia:

    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)