Neste artigo, discutiremos o algoritmo de classificação de bucket. Os itens de dados na classificação de bucket são distribuídos na forma de buckets. Em entrevistas técnicas ou de codificação para engenheiros de software, algoritmos de classificação são amplamente solicitados. Então, é importante discutir o tema.
Bucket sort é um algoritmo de classificação que separa os elementos em vários grupos chamados de buckets. Os elementos na classificação por bucket são primeiro divididos uniformemente em grupos chamados buckets e, em seguida, são classificados por qualquer outro algoritmo de classificação. Depois disso, os elementos são reunidos de forma ordenada.
O procedimento básico para realizar a classificação de balde é fornecido a seguir -
- Primeiro, particione o intervalo em um número fixo de intervalos.
- Em seguida, jogue cada elemento em seu balde apropriado.
- Depois disso, classifique cada bucket individualmente aplicando um algoritmo de classificação.
- E, por fim, concatene todos os buckets classificados.
As vantagens da classificação por balde são -
- A classificação de balde reduz o não. de comparações.
- É assintoticamente rápido devido à distribuição uniforme dos elementos.
As limitações da classificação de bucket são -
- Pode ou não ser um algoritmo de classificação estável.
- Não é útil se tivermos um array grande porque aumenta o custo.
- Não é um algoritmo de classificação local, porque é necessário algum espaço extra para classificar os intervalos.
A complexidade melhor e média da classificação de bucket é O (n + k) , e a complexidade do pior caso da classificação de bucket é Sobre2) , onde n é o número de itens.
A classificação de balde é comumente usada -
- Com valores de ponto flutuante.
- Quando a entrada é distribuída uniformemente em um intervalo.
A ideia básica para realizar a classificação de balde é dada a seguir -
bucketSort(a[], n) 1. Create 'n' empty buckets 2. Do for each array element a[i] 2.1. Put array elements into buckets, i.e. insert a[i] into bucket[n*a[i]] 3. Sort the elements of individual buckets by using the insertion sort. 4. At last, gather or concatenate the sorted buckets. End bucketSort
Agora, vamos ver o algoritmo de classificação de balde.
Algoritmo
Bucket Sort(A[]) 1. Let B[0....n-1] be a new array 2. n=length[A] 3. for i=0 to n-1 4. make B[i] an empty list 5. for i=1 to n 6. do insert A[i] into list B[n a[i]] 7. for i=0 to n-1 8. do sort list B[i] with insertion-sort 9. Concatenate lists B[0], B[1],........, B[n-1] together in order End
Abordagem de dispersão
Podemos entender o algoritmo de classificação Bucket por meio da abordagem de coleta de dispersão. Aqui, os elementos fornecidos são primeiro espalhados em grupos. Após a dispersão, os elementos em cada intervalo são classificados usando um algoritmo de classificação estável. Por fim, os elementos classificados serão reunidos em ordem.
Vamos pegar um array não classificado para entender o processo de classificação por bucket. Será mais fácil entender a classificação do bucket por meio de um exemplo.
Deixe os elementos do array serem -
Agora, crie intervalos com um intervalo de 0 a 25. Os intervalos são de 0 a 5, 5 a 10, 10 a 15, 15 a 20, 20 a 25. Os elementos são inseridos nos buckets de acordo com o intervalo do bucket. Suponha que o valor de um item seja 16, então ele será inserido no intervalo entre 15 e 20. Da mesma forma, cada item da matriz será inserido de acordo.
Esta fase é conhecida por ser a dispersão de elementos da matriz .
Agora, organizar cada balde individualmente. Os elementos de cada intervalo podem ser classificados usando qualquer um dos algoritmos de classificação estáveis.
Afinal, juntar os elementos classificados de cada balde em ordem
Agora, o array está completamente classificado.
Complexidade de classificação de bucket
Agora, vamos ver a complexidade de tempo da classificação do intervalo no melhor caso, no caso médio e no pior caso. Veremos também a complexidade do espaço da classificação do bucket.
1. Complexidade de tempo
| Caso | Tempo | Complexidade |
|---|---|---|
| Melhor caso | O (n + k) | |
| Caso médio | O (n + k) | |
| Pior caso | Sobre2) |
Se usarmos a classificação por inserção para classificar os elementos do balde, a complexidade geral será linear, ou seja, O(n + k), onde O(n) é para fazer os baldes e O(k) é para classificar os elementos do balde usando algoritmos com complexidade de tempo linear na melhor das hipóteses.
A melhor complexidade de tempo da classificação de bucket é O (n + k) .
A complexidade piorará quando os elementos estiverem na ordem inversa.
A complexidade de tempo de pior caso da classificação de bucket é Sobre2) .
2. Complexidade Espacial
| Complexidade Espacial | Ó (n * k) |
| Estábulo | SIM |
- A complexidade do espaço da classificação do bucket é O(n*k).
Implementação de classificação de bucket
Agora, vamos ver os programas de bucket sort em diferentes linguagens de programação.
Programa: Escreva um programa para implementar bucket sort em linguagem C.
#include int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) printf('%d ', a[i]); main() a[]="{54," 12, 84, 57, 69, 41, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of printf('before sorting are -
'); printarr(a, n); bucket(a, printf('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-5.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) // function to get maximum element from the given array { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[], int n) // function to implement bucket sort { int max = getMax(a, n); //max is the maximum element of array int bucket[max], i; for (int i = 0; i <= max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[], int n) function to print array elements ++i) cout< <a[i]<<' '; main() a[]="{34," 42, 74, 57, 99, 84, 9, 5}; n="sizeof(a)" sizeof(a[0]); is the size of cout<<'before sorting are -
'; printarr(a, n); bucket(a, cout<<'
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-6.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in C#.</p> <pre> using System; class Bucket { static int getMax(int[] a) // function to get maximum element from the given array { int n = a.Length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } static void bucket(int[] a) // function to implement bucket sort { int n = a.Length; int max = getMax(a); //max is the maximum element of array int[] bucket = new int[max+1]; for (int i = 0; i <= 10 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; static void printarr(int[] a) * function to print the array int i; n="a.Length;" (i="0;" console.write(a[i] + ' '); main() int[] a="{" 95, 50, 45, 15, 20, }; console.write('before sorting elements are -
'); printarr(a); bucket(a); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-7.webp" alt="bucket sort"> <p> <strong>Program:</strong> Write a program to implement bucket sort in Java.</p> <pre> public class Bucket { int getMax(int a[]) // function to get maximum element from the given array { int n = a.length; int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } void bucket(int a[]) // function to implement bucket sort { int n = a.length; int max = getMax(a); //max is the maximum element of array int bucket[] = new int[max+1]; for (int i = 0; i <= 9 max; i++) { bucket[i]="0;" } for (int i="0;" < n; bucket[a[i]]++; j="0;" 0) a[j++]="i;" bucket[i]--; void printarr(int a[]) * function to print the array int i; n="a.length;" (i="0;" system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 90, 40, 5, 15, 30, }; bucket b1="new" bucket(); system.out.print('before sorting elements are -
'); b1.printarr(a); b1.bucket(a); system.out.print('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/04/bucket-sort-algorithm-8.webp" alt="bucket sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. Along with the algorithm, we have also discussed the bucket sort complexity, working, and implementation in different programming languages.</p> <hr></=></pre></=></pre></=></pre></=>