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. O bucket sort tem complexidade linear (Θ(n)) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos.

[editar] Funcionamento

Bucket sort funciona do seguinte modo:

1. Inicialize um vetor de "baldes", inicialmente vazios.
2. Vá para o vetor original, incluindo cada elemento em um balde.
3. Ordene todos os baldes não vazios.
4. Coloque os elementos dos baldes que não estão vazios no vetor original.

[editar] Exemplo em C

//Compilado em Linux.Sujeito a mudanças caso outro sistema seja utilizado.

#include <stdio.h>

#define tam_bucket 100
#define num_bucket 10
#define max 10

typedef struct {
        int topo;
        int balde[tam_bucket];
}bucket;

void bucket_sort(int v[],int tam);                   //cabeçalho das funções
void bubble(int v[],int tam);                                   
                                                                
//int main(){}                                                  
                                                                 
void bucket_sort(int v[],int tam){                                     
        bucket b[num_bucket];                                      
        int i,j,k;                                                 
/* 1 */ for(i=0;i<num_bucket;i++)                    //inicializa todos os "topo"
                b[i].topo=0;
        
/* 2 */ for(i=0;i<tam;i++){                          //verifica em que balde o elemento deve ficar
                j=(num_bucket)-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--;
                }
        }
        
/* 3 */ for(i=0;i<num_bucket;i++)                     //ordena os baldes
                if(b[i].topo)
                        bubble(b[i].balde,b[i].topo);
        
        i=0;
/* 4 */ for(j=0;j<num_bucket;j++){                    //põe os elementos dos baldes de volta no vetor
                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;
                }
}

[editar] Explicação do código

Antes de mais nada, é preciso saber o que cada "#define" significa.

1. tam_bucket é o tamanho de cada balde da estrutura bucket.
2. num_bucket é o número de baldes, isto é, o tamanho do vetor de bucket
3. max é o tamanho do vetor a ser ordenado.

A estrutura bucket consiste de um vetor de inteiros (int balde[tam_bucket]) e de uma variável que serve para dizer quantos números estão armazenados no balde.

O parâmetro "tam", tanto na função "bucket_sort" como na "bubble", é o tamanho do vetor a ser ordenado.

A explicação dos "for" agora:

1. Inicializa o "topo" de cada bucket que o vetor de bucket "b[num_bucket]" contém.

   Isso é importante, pois, a princípio, os baldes estão vazios.

2. Verifica em que balde o elemento deve ficar.

   Cada elemento do vetor a ser ordenado é colocado em seu lugar no vetor de bucket.Por exemplo, suponha o número 26.A variável "j" receberia (num_bucket-1), isto é,9 no exemplo acima.O "while" verifica se 26 é maior do que j*10 (90).Como isto não é válido, "j" é decrementado em 1, e o processo se repete até que j=2, já que 26>=20.Então, o balde de posição 2 recebe 26.Caso não haja nenhum outro elemento no balde 2, isso significa que "topo" daquele balde vale 0, portanto balde[0] recebe o 26.Caso haja, por exemplo, 3 elementos no balde, isso quer dizer que topo=2, portanto balde[2] recebe 26.Depois disso, "topo" daquele balde é incrementado em 1 e o processo se repete para os outros elementos do vetor que queremos ordenar.

3. Ordena cada balde.

   Ordena os baldes cujos "topo" são diferentes de 0, ou seja, não estão vazios.No algoritmo acima, o bubble sort foi utilizado, mas métodos mais eficientes podem ser utilizados.

4. Por fim, os baldes são percorridos e seus elementos são devolvidos para o vetor original.

Atente para o fato de que nosso exemplo não ordena elementos negativos.Um tratamento especial para eles seria necessário.Além do mais, o método de separar cada elemento pode ser diferente.O utilizado foi verificar se o elemento está entre 0 e 10, 11 e 20, e assim por diante.