In questo articolo discuteremo dell'algoritmo di ordinamento dei bucket. Gli elementi di dati nell'ordinamento per bucket vengono distribuiti sotto forma di bucket. Nelle interviste di codifica o tecniche per ingegneri del software, gli algoritmi di ordinamento sono ampiamente richiesti. Quindi è importante discutere l’argomento.
L'ordinamento dei bucket è un algoritmo di ordinamento che separa gli elementi in più gruppi detti bucket. Gli elementi nell'ordinamento per contenitori vengono prima divisi uniformemente in gruppi chiamati contenitori, quindi vengono ordinati mediante qualsiasi altro algoritmo di ordinamento. Successivamente, gli elementi vengono raccolti in modo ordinato.
La procedura di base per eseguire l'ordinamento del bucket è la seguente:
- Innanzitutto, suddividi l'intervallo in un numero fisso di bucket.
- Quindi, getta ogni elemento nel secchio appropriato.
- Successivamente, ordina ciascun contenitore individualmente applicando un algoritmo di ordinamento.
- E infine, concatena tutti i bucket ordinati.
I vantaggi dell'ordinamento a secchio sono:
- L'ordinamento dei secchi riduce il n. di confronti.
- È asintoticamente veloce a causa della distribuzione uniforme degli elementi.
Le limitazioni dell'ordinamento dei bucket sono:
- Potrebbe essere o meno un algoritmo di ordinamento stabile.
- Non è utile se abbiamo un array di grandi dimensioni perché aumenta il costo.
- Non è un algoritmo di ordinamento sul posto, poiché è necessario spazio aggiuntivo per ordinare i contenitori.
La complessità migliore e nel caso medio dell'ordinamento del bucket è O(n+k) , e la complessità dell'ordinamento del bucket nel caso peggiore è SU2) , Dove N è il numero di elementi.
L'ordinamento per bucket è comunemente utilizzato:
- Con valori in virgola mobile.
- Quando l'input è distribuito uniformemente su un intervallo.
L'idea di base per eseguire l'ordinamento del bucket è data come segue:
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
Ora vediamo l'algoritmo del bucket sort.
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
Approccio di raccolta e dispersione
Possiamo comprendere l'algoritmo di ordinamento del bucket tramite l'approccio scatter-gather. Qui gli elementi forniti vengono prima sparsi in secchi. Dopo la dispersione, gli elementi in ciascun contenitore vengono ordinati utilizzando un algoritmo di ordinamento stabile. Alla fine, gli elementi ordinati verranno raccolti in ordine.
Prendiamo un array non ordinato per comprendere il processo di ordinamento del bucket. Sarà più semplice comprendere l'ordinamento dei bucket tramite un esempio.
Lascia che gli elementi dell'array siano -
Ora crea bucket con un intervallo compreso tra 0 e 25. Gli intervalli di bucket sono 0-5, 5-10, 10-15, 15-20, 20-25. Gli elementi vengono inseriti nei contenitori in base alla gamma dei contenitori. Supponiamo che il valore di un articolo sia 16, quindi verrà inserito nel bucket con intervallo 15-20. Allo stesso modo, ogni elemento dell'array verrà inserito di conseguenza.
Questa fase è nota per essere la dispersione degli elementi dell'array .
Ora, ordinare ogni secchio individualmente. Gli elementi di ciascun bucket possono essere ordinati utilizzando uno qualsiasi degli algoritmi di ordinamento stabili.
Infine, raccogliere gli elementi ordinati da ciascun bucket in ordine
Ora l'array è completamente ordinato.
Complessità dell'ordinamento dei bucket
Ora, vediamo la complessità temporale dell'ordinamento dei bucket nel caso migliore, nel caso medio e nel caso peggiore. Vedremo anche la complessità spaziale del bucket sort.
1. Complessità temporale
| Caso | Tempo | Complessità |
|---|---|---|
| Caso migliore | O(n+k) | |
| Caso medio | O(n+k) | |
| Caso peggiore | SU2) |
Se utilizziamo l'ordinamento per inserimento per ordinare gli elementi del bucket, la complessità complessiva sarà lineare, ovvero O(n + k), dove O(n) serve per creare i bucket e O(k) serve per ordinare gli elementi del bucket utilizzando algoritmi con complessità temporale lineare nel migliore dei casi.
La complessità temporale del bucket sort nel migliore dei casi è O(n+k) .
La complessità peggiorerà quando gli elementi saranno nell’ordine inverso.
La complessità temporale del bucket sort nel caso peggiore è SU2) .
2. Complessità spaziale
| Complessità spaziale | O(n*k) |
| Stabile | SÌ |
- La complessità spaziale del bucket sort è O(n*k).
Implementazione del bucket sort
Vediamo ora i programmi di bucket sort nei diversi linguaggi di programmazione.
Programma: Scrivere un programma per implementare il bucket sort in linguaggio 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></=>