Funcionamento

Bucket sort funciona do seguinte modo:

Inicialize um vetor de "baldes", inicialmente vazios.

Vá para o vetor original, incluindo cada elemento
em um balde.

Ordene todos os baldes não vazios.

Coloque os elementos dos baldes que não estão
vazios no vetor original.
BucketSort em C
/* Explicação do código
Antes de mais nada, é preciso saber o que cada "#define" significa.
tam_bucket é o tamanho de cada balde da estrutura bucket.
num_bucket é o número de baldes, isto é, o tamanho do vetor de bucket
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.
*/
BucketSort em C
#include <stdio.h>
/* printf, scanf, puts, NULL */
#include <stdlib.h> /* srand, rand */
#include <time.h>
/* time */
#define tam_bucket 100
#define num_bucket 10
#define max 100
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);
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);