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 | |
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
[editar | editar código-fonte]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
[editar | editar código-fonte]//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
[editar | editar código-fonte]- 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
[editar | editar código-fonte]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
[editar | editar código-fonte]/*
* 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
[editar | editar código-fonte]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)
Ver também
[editar | editar código-fonte]Referências
[editar | editar código-fonte]- ↑ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2012). Algoritmos: teoria e prática. Rio de Janeiro: Elsevier. pp. 145–146–147. ISBN 9788535236996
- ↑ «Bucket Sort in Python». Stack Abuse (em inglês). 26 de junho de 2020. Consultado em 24 de setembro de 2021
Ligações externas
[editar | editar código-fonte]