Bucket Sort

Um exemplo de ordenação por distribuição é o algoritmo bucket sort (ordenação balde). Esse algoritmo cria “baldes” com valores atribuídos a estes, esses baldes receberão os números referente ao seu valor depois estes são “esvaziados” seguindo a ordem.
Exemplo vetor = {2,1,3,5,1,3,3,5,4,2}
Levando em consideração o exemplo acima, seria necessário a criação dos baldes 1, 2, 3, 4 e 5. Os números seriam distribuídos nos baldes da seguinte forma:

 Após isso, basta esvaziar os baldes a partir do primeiro para que os números fiquem na ordem.
Os baldes não necessariamente precisam ser numerados dessa forma, para um conjunto muito grande de números a quantidade de baldes seria muito grande e podemos ainda encontrar vetores que não possuem números repetidos, assim, a criação de um balde para cada vetor faz com que a ordenação se torne muito trabalhosa. Para organizar um conjunto grande de número que não se repetem cada balde pode ter um intervalo. Por exemplo: balde 1 receberá número de 0 a 9, balde 2 de 10 a 19, balde 3 de 20 a 29 e assim por diante. Implementação do bucket sort em C (EPPSTEIN, 1996):

#include

 #define tam_balde 100
 #define num_balde 10
 #define max 10

 typedef struct {
         int topo;
         int balde[tam_balde];
 }balde;

 void bucket_sort(int v[],int tam){
     balde b[num_balde];
     int i,j,k;
     for(i=0;i<num_balde;i++)
             b[i].topo=0;

     for(i=0;i<tam;i++){
             j=(num_balde)-1;
             while(1){
                     if(j<0)
                             break;
                     if(v[i]>=j*10){
                             b[j].balde[b[j].topo]=v[i];
                             (b[j].topo)++;
                             break;
                     }
                     j--;
             }
     }

     for(i=0;i<num_balde;i++)
             if(b[i].topo)
                     bubble(b[i].balde,b[i].topo);

     i=0;
     for(j=0;j<num_balde;j++){
             for(k=0;k<b[j].topo;k++){
                     v[i]=b[j].balde[k];
                     i++;
             }
     }
 }

void bubble(int v[],int tam){
    int i,j,temp,flag;
    if(tam)
    for(j=0;j<tam-1;j++){
        flag=0;
        for(i=0;i<tam-1;i++){
            if(v[i+1]<v[i]){
                temp=v[i];
                v[i]=v[i+1];
                v[i+1]=temp;
                flag=1;
            }
        }
        if(!flag)
        break;
    }
}

int main(int argc, char *argv[])
{
    int v[6] = {5,3,7,1,2,9}, i, j, aux, menor, pos;
    bucket_sort(v, 6);

    //mostrar vetor ordenado
    printf("\nVetor ordenado: ");
    for(i=0;i<6;i++)
        printf("%d, ", v[i]);

}

Observe no código acima que o bucket sort não é exatamente um algoritmo de ordenação, mas sim uma distribuição para tornar a organização mais efetiva. Por esse motivo é encontrado no código a função bubble, que é utilizada para organizar os elementos dentro de cada balde. Pode-se substituir o bubble sort por qualquer outro algoritmo de ordenação.