En este artículo, analizaremos el algoritmo de clasificación de depósitos. Los elementos de datos en la clasificación de depósitos se distribuyen en forma de depósitos. En entrevistas técnicas o de codificación para ingenieros de software, los algoritmos de clasificación son muy solicitados. Por eso es importante discutir el tema.
La clasificación de depósitos es un algoritmo de clasificación que separa los elementos en varios grupos que se denominan depósitos. Los elementos de la clasificación por depósitos primero se dividen uniformemente en grupos llamados depósitos y luego se clasifican mediante cualquier otro algoritmo de clasificación. Después de eso, los elementos se reúnen de forma ordenada.
El procedimiento básico para realizar la clasificación del cubo se detalla a continuación:
- Primero, divida el rango en una cantidad fija de depósitos.
- Luego, tira cada elemento en su cubo correspondiente.
- Después de eso, clasifique cada depósito individualmente aplicando un algoritmo de clasificación.
- Y por último, concatene todos los depósitos ordenados.
Las ventajas de la clasificación por cubos son:
- La clasificación de cubos reduce el no. de comparaciones.
- Es asintóticamente rápido debido a la distribución uniforme de elementos.
Las limitaciones de la clasificación de depósitos son:
- Puede que sea o no un algoritmo de clasificación estable.
- No sirve de nada si tenemos un conjunto grande porque aumenta el coste.
- No es un algoritmo de clasificación in situ, porque se requiere algo de espacio adicional para clasificar los depósitos.
La complejidad mejor y promedio de la clasificación de depósitos es O(norte + k) , y la complejidad del peor de los casos de clasificación de depósitos es En2) , dónde norte es el número de elementos.
La clasificación por cubos se utiliza habitualmente:
- Con valores de coma flotante.
- Cuando la entrada se distribuye uniformemente en un rango.
La idea básica para realizar la clasificación del cubo se da a continuación:
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
Ahora, veamos el algoritmo de clasificación de depósitos.
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
Enfoque de dispersión
Podemos comprender el algoritmo de clasificación de Bucket mediante un enfoque de dispersión y recopilación. Aquí, los elementos dados se distribuyen primero en cubos. Después de la dispersión, los elementos de cada depósito se clasifican mediante un algoritmo de clasificación estable. Por fin, los elementos ordenados se reunirán en orden.
Tomemos una matriz sin clasificar para comprender el proceso de clasificación de depósitos. Será más fácil entender la clasificación de depósitos con un ejemplo.
Dejemos que los elementos de la matriz sean:
Ahora, cree depósitos con un rango de 0 a 25. Los rangos de depósitos son 0-5, 5-10, 10-15, 15-20, 20-25. Los elementos se insertan en los cubos según el rango del cubo. Supongamos que el valor de un artículo es 16, por lo que se insertará en el depósito con el rango 15-20. De manera similar, cada elemento de la matriz se insertará en consecuencia.
Se sabe que esta fase es la dispersión de elementos de matriz .
Ahora, clasificar cada cubo individualmente. Los elementos de cada depósito se pueden ordenar utilizando cualquiera de los algoritmos de clasificación estables.
Por fin, recolectar los elementos ordenados de cada cubo en orden
Ahora, la matriz está completamente ordenada.
Complejidad de clasificación de depósitos
Ahora, veamos la complejidad temporal de la clasificación de depósitos en el mejor de los casos, en el caso promedio y en el peor de los casos. También veremos la complejidad espacial del tipo cubo.
1. Complejidad del tiempo
| Caso | Tiempo | Complejidad |
|---|---|---|
| Mejor caso | O(norte + k) | |
| Caso promedio | O(norte + k) | |
| Peor de los casos | En2) |
Si utilizamos la ordenación por inserción para ordenar los elementos del depósito, la complejidad general será lineal, es decir, O(n + k), donde O(n) es para hacer los depósitos y O(k) es para ordenar los elementos del depósito. utilizando algoritmos con complejidad de tiempo lineal en el mejor de los casos.
La complejidad temporal del mejor de los casos para la clasificación de depósitos es O(norte + k) .
La complejidad empeorará cuando los elementos estén en orden inverso.
La complejidad temporal del peor de los casos para la clasificación de depósitos es En2) .
2. Complejidad espacial
| Complejidad espacial | O(n*k) |
| Estable | SÍ |
- La complejidad espacial de la clasificación por depósitos es O (n*k).
Implementación de clasificación de cubos.
Ahora, veamos los programas de clasificación de depósitos en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar la clasificación de depósitos en lenguaje 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></=>