PT

Bucket sort

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){displaystyle Theta (n)}

quando o vetor a ser ordenado contém valores que são uniformemente distribuídos[1].

Bucket sort
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso

O(n2){displaystyle O(n^{2})}

complexidade caso médio

O(n+k){displaystyle O(n+k)}

complexidade melhor caso

O(n+k){displaystyle O(n+k)}

Algoritmos
Esta caixa:

Conceito de base do bucket sort.

. . . Bucket sort . . .

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.
//Compilado em Linux.Sujeito a mudanças caso outro sistema seja utilizado.  #include   #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;inum_bucket;i++)                    //inicializa todos os "topo"                 b[i].topo=0;          /* 2 */ for(i=0;itam;i++){                          //verifica em que balde o elemento deve ficar                j=(num_bucket)-1;                 while(1){                         if(j0)                                 break;                         if(v[i]>=j*10){                                 b[j].balde[b[j].topo]=v[i];                                 (b[j].topo)++;                                 break;                         }                         j--;                 }         }          /* 3 */ for(i=0;inum_bucket;i++)                     //ordena os baldes                 if(b[i].topo)                         bubble(b[i].balde,b[i].topo);                  i=0; /* 4 */ for(j=0;jnum_bucket;j++){                    //põe os elementos dos baldes de volta no vetor                 for(k=0;kb[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;jtam-1;j++){                         flag=0;                         for(i=0;itam-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;                 } }

. . . Bucket sort . . .

Este artigo foi publicado a partir do site Wikipedia. O artigo original pode ser um pouco reduzido ou modificado. Alguns links podem ter sido modificados. O texto está licenciado sob “Creative Commons – Atribuição – Compartilhamento” [1] e parte do texto também pode ser licenciado sob os termos da “GNU Free Documentation License” [2]. Termos adicionais podem ser aplicados aos arquivos de mídia. Ao usar este site, você concorda com nossas páginas jurídicas. Links da Web: [1] [2]

. . . Bucket sort . . .

Back To Top