En este artículo, analizaremos el algoritmo de clasificación de conteo. La clasificación por conteo es una técnica de clasificación que se basa en las claves entre rangos específicos. 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.
opacidad de transición css
Esta técnica de clasificación no realiza la clasificación comparando elementos. Realiza la clasificación contando objetos que tienen valores clave distintos, como hash. Después de eso, realiza algunas operaciones aritméticas para calcular la posición del índice de cada objeto en la secuencia de salida. La clasificación por conteo no se utiliza como algoritmo de clasificación de propósito general.
La clasificación por conteo es efectiva cuando el rango no es mayor que el número de objetos a clasificar. Se puede utilizar para ordenar los valores de entrada negativos.
Ahora, veamos el algoritmo de clasificación por conteo.
Algoritmo
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
Funcionamiento del algoritmo de clasificación de conteo
Ahora, veamos el funcionamiento del algoritmo de clasificación de conteo.
Para comprender el funcionamiento del algoritmo de clasificación por conteo, tomemos una matriz sin clasificar. Será más fácil entender el tipo de conteo mediante un ejemplo.
Dejemos que los elementos de la matriz sean:
1. Encuentre el elemento máximo de la matriz dada. Dejar máximo ser el elemento máximo.
2. Ahora, inicializa la matriz de longitud. máximo + 1 teniendo los 0 elementos. Esta matriz se utilizará para almacenar el recuento de elementos en la matriz dada.
3. Ahora, tenemos que almacenar el recuento de cada elemento de la matriz en su índice correspondiente en la matriz de recuento.
El recuento de un elemento se almacenará como: Supongamos que el elemento de matriz '4' aparece dos veces, por lo que el recuento del elemento 4 es 2. Por lo tanto, 2 se almacena en el 4thposición de la matriz de conteo. Si algún elemento no está presente en la matriz, coloque 0, es decir, suponga que el elemento '3' no está presente en la matriz, por lo tanto, 0 se almacenará en 3.terceroposición.
Ahora, almacene la suma acumulada de contar elementos de la matriz. Será útil colocar los elementos en el índice correcto de la matriz ordenada.
De manera similar, el recuento acumulado de la matriz de recuento es:
4. Ahora, encuentre el índice de cada elemento de la matriz original.
Después de colocar el elemento en su lugar, disminuya su cuenta en uno. Antes de colocar el elemento 2, su conteo era 2, pero luego de colocarlo en su posición correcta, el nuevo conteo para el elemento 2 es 1.
De manera similar, después de ordenar, los elementos de la matriz son:
Ahora, la matriz está completamente ordenada.
Contando la complejidad de clasificación
Ahora, veamos la complejidad temporal del ordenamiento por conteo 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 de conteo.
1. Complejidad del tiempo
| Caso | Tiempo | Complejidad |
|---|---|---|
| Mejor caso | O(norte + k) | |
| Caso promedio | O(norte + k) | |
| Peor de los casos | O(norte + k) |
En todos los casos anteriores, la complejidad temporal de la clasificación por conteo es la misma. Esto se debe a que el algoritmo pasa por n+k veces, independientemente de cómo se coloquen los elementos en la matriz.
La clasificación por conteo es mejor que las técnicas de clasificación basadas en comparación porque no hay comparación entre elementos en la clasificación por conteo. Pero, cuando los números enteros son muy grandes, la ordenación por conteo es mala porque es necesario crear matrices de ese tamaño.
2. Complejidad espacial
| Complejidad espacial | O(máx.) |
| Estable | SÍ |
- La complejidad espacial de la clasificación por conteo es O (máx.). Cuanto mayor sea la gama de elementos, mayor será la complejidad del espacio.
Implementación de clasificación por conteo.
Ahora, veamos los programas de clasificación por conteo en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar la clasificación por conteo en lenguaje C.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; 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/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; 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/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); 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/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting 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. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> Producción
numeroso único
Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.
Este artículo no se limitó sólo al algoritmo. También hemos discutido el conteo de la complejidad de clasificación, el trabajo y la implementación en diferentes lenguajes de programación.