Contando complejidad de clasificación

¿Qué está contando??

El tipo de contar se ilustra mejor con la clasificación de enteros. En C/C ++ y Java, los personajes son enteros y se pueden ordenar en la forma en que se ordenan los enteros. Considere la siguiente lista no organizada de enteros:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

Esta lista se clasifica en orden ascendente. Se puede dar (recibido por el programa de clasificación) como una matriz. Consiste en números positivos mayores o iguales a 0.

Observe aquí que el entero más alto es de 20. Entonces, 20 + 1 = 21, se deben proporcionar nuevas ubicaciones de matriz. El adicional 1 es por la posibilidad de que uno de los enteros se ordene es 0. Recuerde que el programa de clasificación no sabe los números que se ordenarán de antemano. Entonces, se debe hacer la posibilidad de tener 0.

Para cada índice de la nueva matriz que corresponde a un valor en la lista dada, el número de ocurrencia del valor en la lista dada se asigna como el valor para esa nueva celda de matriz. Es decir, la nueva matriz consta de contadores. La lista anterior no organizada se representa de la siguiente manera:

0	0	0	0	0	0	0	0	1	0	1	0	3	0	1	0	1	0	2	0	1
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	dieciséis	17	18	19	20

Esta tabla representa una matriz que es la nueva matriz de contadores. En esta etapa, hay dos matrices: la matriz dada de la lista sin clasificar y la matriz de contadores llamado la matriz de conteo.

En la tabla, la segunda fila tiene los índices. La primera fila tiene los recuentos. Cada recuento es el número de ocurrencia del índice correspondiente que se encuentra como el valor en la lista no organizada.

Para los índices 0 a 7 (inclusive), el recuento es 0. Esto se debe a que ninguno de estos índices es un valor en la lista no organizada dada. El índice 8 ocurre una vez en la lista, por lo que su recuento es 1. El índice 9 ocurre cero veces en la lista, por lo que su recuento es 0. El índice 10 ocurre una vez en la lista, por lo que su recuento es 1. El índice 12 ocurre tres veces en la lista, por lo que su recuento es 3. El índice 13 ocurre cero veces en la lista, por lo que su recuento es 0. Esto continúa hasta el índice 20 con un recuento de 1, mientras que el índice 18 tiene un recuento de 2.

La lista ordenada es la siguiente:

8, 10, 12, 12, 12, 14, 16, 18, 18, 20

Esto se puede obtener de la matriz de recuento (nueva) de la siguiente manera:

Mover de izquierda a derecha, si el valor de un índice es 0, ese valor no está en la lista no organizada dada (matriz). Si el valor es 1, escriba el índice una vez. Si el valor es 2, escriba el índice dos veces. Si el valor es 3, escriba el índice tres veces. Si el valor es 4, escriba el índice 4 veces, y así sucesivamente. Todo esto se puede hacer en la matriz no organizada dada (lista).

Algoritmo de clasificación de contabilidad

• Proporcione una matriz cuya longitud es el número máximo en la lista no organizada, más 1 (para tener en cuenta un posible 0 en la lista). El índice de esta matriz es un posible valor en la lista no organizada.
• Lea la matriz de conteo de izquierda a derecha y luego escriba el índice cuyo valor no es 0 y el número de veces para el valor de la celda del índice.

Operaciones

El algoritmo tiene dos pasos. Para la lista dada anterior, el primer paso tiene 10 operaciones principales porque el número de elementos en la lista no organizada es 10. El segundo paso tiene 21 operaciones principales porque el valor máximo en la lista no organizada es 20 (el 1 adicional es para un valor de 0 posible). Entonces, el número de operaciones principales se considera de la siguiente manera:

O (10 + 20)

Donde 10 es el número de elementos en la lista no organizada y 20 es el valor máximo en la lista no organizada. El 1 a 20 agregado se ignora en este punto, pero tenga en cuenta que tiene que ser codificado.

Complejidad del tiempo para contar clasificaciones

La complejidad del tiempo es el número aproximado de las operaciones principales para algún código. La complejidad del tiempo indica la velocidad del código. La complejidad del tiempo para contar se da de la siguiente manera:

O (N + M)

Donde n es el número de elementos (longitud o tamaño) de la matriz no organizada dada, y M es el valor máximo en la matriz no organizada dada. El 1 a M agregado se ignora en este punto. El Big-O con sus paréntesis y contenido se conoce como la notación Big-O.

Tenga en cuenta que para obtener el valor máximo en la matriz, algunas operaciones deben ocurrir en el código. Sin embargo, estas operaciones se ignoran al citar la complejidad del tiempo.

La matriz de recuentos debe tener todos sus elementos inicialmente hechos como cero. Todas estas operaciones también se ignoran al citar la complejidad del tiempo para el tipo de conteo.

Espacio de memoria

Observe que en la matriz de recuentos anterior, todos los recuentos de 0 son redundantes. Aunque sus espacios son redundantes en la memoria, tienen que estar allí. El tipo de conteo requiere espacio de memoria innecesario en general. Nada se hace normalmente para evitar las ubicaciones redundantes. Si se puede conocer el valor mínimo en la matriz no armada dada, se puede omitir la parte inicial de la matriz de recuento para reducir el espacio. Sin embargo, los ceros intercalados en la matriz de recuentos no se pueden omitir.

Nota: También hay complejidad espacial, pero eso no se aborda en este artículo.

Codificación en C

Una función de clasificación de conteo en el lenguaje de la computadora C es la siguiente:

Void CountingSort (int arr [], int n)
int max = 0;
para (int i = 0; i max)
max = arr [i];


int count [max+1];
para (int i = 0; i< max+1; i++)
contar [i] = 0;

//norte
para (int i = 0; i< n; i++)
Count [arr [i]] = count [arr [i]] + 1; // Agregar 1 para cada ocurrencia

//metro
int k = 0; // índice para matriz dada
para (int i = 0; iif (contar [i] != 0)
para (int j = 0; jarr [k] = i; // Poner el valor ordenado en una matriz dada
K ++;

El bucle y la entrada anidados son los siguientes:

16, 20, 12, 10, 18, 8, 12, 18, 12, 14

En realidad hay 24 operaciones principales y no 20. La operación adicional 3 + 1 = 4 se ignora al citar la complejidad del tiempo para el tipo de conteo.

Una función principal C adecuada es la siguiente:

int main (int argc, char ** argv)

int n = 10;
int arr [] = 16, 20, 12, 10, 18, 8, 12, 18, 12, 14;
Countingsort (arr, n);
para (int i = 0; iprintf ("%d", arr [i]);
printf ("\ n");
regresar 0;

La salida es:

8 10 12 12 12 14 16 18 18 20

Conclusión

La complejidad del tiempo para el tipo de conteo es:

O (N + M)

Donde m generalmente es mayor que n, n es el número de elementos (longitud) de la lista no organizada dada, y M es el elemento máximo en la lista no organizada dada.