Bucket sort
Bucket sort | |
---|---|
classe | Algoritmo de ordenação |
estrutura de dados | Array, Listas ligadas |
complexidade pior caso | |
complexidade caso médio | |
complexidade melhor caso | |
Algoritmos | |
Esta caixa:
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8f/Bucket_sort_concept.svg/250px-Bucket_sort_concept.svg.png)
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 quando o vetor a ser ordenado contém valores que são uniformemente distribuídos[1].
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.
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); 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; } }
Explicação do código
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/61/Bucket_sort_1.png/250px-Bucket_sort_1.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/39/Bucket_sort_2.png/250px-Bucket_sort_2.png)
- 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çãobucket_sort
como nabubble
, é o tamanho do vetor a ser ordenado.
- A explicação dos
for
agora:
- Inicializa o
topo
de cada bucket que o vetor de bucketb[num_bucket]
contém;- Isso é importante, pois, a princípio, os baldes estão vazios;
- 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
receberianum_bucket-1
, isto é, 9 no exemplo acima. Owhile
verifica se 26 é maior do quej*10
(90). Como isto não é válido,j
é decrementado em 1, e o processo se repete até quej=2
, já que26>=20
. Então, o balde de posição 2 recebe 26. Caso não haja nenhum outro elemento no balde 2, isso significa quetopo
daquele balde vale 0, portantobalde[0]
recebe o 26. Caso haja, por exemplo, 3 elementos no balde, isso quer dizer quetopo=2
, portantobalde[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;
- 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
- Ordena cada balde;
- Ordena os baldes cujos
topos
sejam 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;
- Ordena os baldes cujos
- Por fim, os baldes são percorridos e seus elementos são devolvidos para o vetor original.
Atente-se para o fato de que o 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.
Exemplo em C++ com matriz
Aqui uma matriz linear de inteiros com n
elementos, é usado para ordenar os elementos do vetor.
/*************************INICIO*****************************************/ //================================================================== // // Projeto: Bucket Sort // Data de Criacao: 27/02/09 // Autor: Albany Timbo Mesquita // Colaboracao:Pedro Henrique Fernandes Marques Leitao // //================================================================== #include <iostream> #define TAM 20 /*Tamanho do vetor*/ #define NUM 10000 /*base para gerador de numeros aleatorios*/ using std::cout; using std::cin; using std::endl; void gerarVet(int*); void bucketSort(int*); void imprimaVet(int*); int main(){ int vet[TAM],tinicio,tfim,tempo; tinicio=time(NULL); gerarVet(vet); imprimaVet(vet); bucketSort(vet); imprimaVet(vet); tfim=time(NULL); tempo=difftime(tfim,tinicio); cout<<"Tempo de execucao "<<tempo/60<<" Minutos e "<<tempo%60<<" segundos.\n"; system("pause"); return 0; } /***********************************************************************/ /*******************************FUNCOES*********************************/ /***********************************************************************/ void bucketSort(int *vet){ int mat[10][TAM],aux[TAM],cont=1,num,w=0,i,j; do{ for(i=0;i<TAM;i++){aux[i] = 0;}//Zerando o vetor auxiliar. for(i=0;i<10;i++) {//Setando a Matriz com valores -1 for(j=0;j<TAM;j++){ mat[i][j] = -1; } } for (i=0;i<TAM;i++) { num = (vet[i]/cont)%10;//verificando o valor da esquerda para direita mat[num][aux[num]] = vet[i];//colocando o valor na sua posicao na matriz aux[num]++; //contador de colunas da matriz } for(i=0;i<10;i++) {//volta com os valores da Matriz para o vetor for(j=0;j<TAM;j++){ if(mat[i][j] != -1){ vet[w] = mat[i][j]; w++; } } } w = 0; cont=cont*10; }while(aux[0] < TAM);//condicao :Enquanto vetor auxiliar < tamanho vetor } // /******************GERADOR DE NUMEROS ALEATORIOS**************************/ void gerarVet(int *vet){ srand(time(NULL)); for (int i=0;i<TAM;i++){ vet[i]=rand()%NUM; } } /*******************FUNCAO PARA IMPRIMIR VETOR************************/ void imprimaVet(int *vet){ for (int i=0;i<TAM;i++){ cout<<vet[i]<<"|"; } cout<<"**************************************************************\n"; } /********************************FIM*************************************/
Exemplo em Java com LinkedList
/* * Autor: wilhs * Data: 28/04/2011 * Crédito: Implementação com base neste Artigo. */ public static void BucketSort(int[] vetor, int maiorValor) { int numBaldes = maiorValor/5; LinkedList[] B = new LinkedList[numBaldes]; for (int i = 0; i < numBaldes; i++){ B[i] = new LinkedList<Integer>(); } //Coloca os valores no balde respectivo: for (int i = 0; i < vetor.length; i++) { int j = numBaldes-1; while (true){ if(j<0){ break; } if(vetor[i] >= (j*5)){ B[j].add(vetor[i]); break; } j--; } } //Ordena e atualiza o vetor: int indice = 0; for (int i = 0; i < numBaldes; i++){ int[] aux = new int[B[i].size()]; //Coloca cada balde num vetor: for (int j = 0; j < aux.length; j++){ aux[j] = (Integer)B[i].get(j); } insertionSort(aux); //algoritmo escolhido para ordenação. // Devolve os valores ao vetor de entrada: for (int j = 0; j < aux.length; j++, indice++){ vetor[indice] = aux[j]; } } }
Exemplo em Python
def bucket_sort(input_list): # Find maximum value in the list and use length of the list to determine which value in the list goes into which bucket max_value = max(input_list) size = max_value/len(input_list) # Create n empty buckets where n is equal to the length of the input list buckets_list= [] for x in range(len(input_list)): buckets_list.append([]) # Put list elements into different buckets based on the size for i in range(len(input_list)): j = int (input_list[i] / size) if j != len (input_list): buckets_list[j].append(input_list[i]) else: buckets_list[len(input_list) - 1].append(input_list[i]) # Sort elements within the buckets using Insertion Sort for z in range(len(input_list)): insertion_sort(buckets_list[z]) # Concatenate buckets with sorted elements into a single list final_output = [] for x in range(len (input_list)): final_output = final_output + buckets_list[x] return final_output def insertion_sort(bucket): for i in range (1, len (bucket)): var = bucket[i] j = i - 1 while (j >= 0 and var < bucket[j]): bucket[j + 1] = bucket[j] j = j - 1 bucket[j + 1] = var def main(): input_list = [1.20, 0.22, 0.43, 0.36,0.39,0.27] print('ORIGINAL LIST:') print(input_list) sorted_list = bucket_sort(input_list) print('SORTED LIST:') print(sorted_list)
[2]
Ver também
- Quick sort
- Heapsort
- Merge sort
- Selection sort
- Insertion sort
- Radix sort
- Bubble sort
Referências
Ligações externas
- Vídeo explicando o Bucket Sort
Portal das tecnologias de informação