Bucket sort

Bucket Sort
O Bucket sort é um algoritmo de ordenação por caixas, possivelmente o algoritmo mais simples de ordenação por distribuição. O requisito essencial é que o tamanho do universo seja um m pequeno e constante.
Por exemplo, suponha que estejamos ordenando elementos de retirados de {0,1,...,m-1}, isto é, o conjunto dos inteiros no intervalo [0,m-1]. A ordenação por caixas usa m contadores. O i-ésimo contador guarda o numero de ocorrências do i-ésimo elemento do universo.
Dados
3 | 1 | 4 | 1 | 5 | 9 | 2 | 6 | 5 | 4 |

Contadores 0 | 2 | 1 | 1 | 2 | 2 | 1 | 0 | 0 | 1 | 0 1 2 3 4 5 6 7 8 9
Dados
1 | 1 | 2 | 3 | 4 | 4 | 5 | 5 | 6 | 9 |

Implementação
Apresentamos a classe BucketSorter. Esse ordenador é projetado para ordenar especificamente um vetor de inteiros. A classe BucketSorter contém dois campos, m e count. O inteiro m especifica o tamanho do universo. A variável count é um vetor de inteiros usado para contar o numero de ocorrências de cada elemento do conjunto universo.
O construtor da classe BucketSorter recebe um único parâmetro que especifica o tamanho do conjunto universo. A variável m recebe o valor especificado, e o vetor count é inicializado com o tamanho requerido.
O método sort(int[ ] array) começa atribuindo zero a todos os contadores. Isso é feito em O(m).
A seguir, uma única passada nos dados conta o numero de ocorrências de cada elemento do universo. Uma vez que cada elemento do universo é examinado exatamente uma vez, o tempo de processamento é O(n).
No passo final, a sequencia ordenada de saída é criada. Uma vez que essa sequencia contem exatamente n itens, o corpo do loop interno é executado exatamente n vezes.
Durante a i-ésima operação do loop externo, o teste de parada do loop interno é avaliado count[i]+1 vezes. Assim, o tempo total de processamento do passo final