Bucket sort
Origem: Wikipédia, a enciclopédia livre.
Bucket sort, ou bin sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo Bucket sort recursivamente. Bucket sort tem complexidade linear (Θ(n)) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos.
Bucket sort funciona assim:
- Inicialize um vetor de "baldes" inicialmente vazios com um tamanho igual ao número de elementos.
- Vá para o vetor original, incluindo cada elemento em um balde dependendo de seu tamanho.
- Ordene todos os baldes não vazios.
- Coloque os elementos do balde não-vazio no vetor original.