Ordenar por conteo en Java

En esta guía, aprenda la teoría detrás de Counting Sort y cómo implementar Counting Sort en Java, con análisis de tiempo y complejidad.

Introducción

La clasificación es una de las técnicas fundamentales utilizadas en la resolución de problemas, especialmente en aquellos relacionados con la escritura e implementación de algoritmos eficientes.

Por lo general, la clasificación se combina con la búsqueda, lo que significa que primero clasificamos elementos en la colección dada, luego buscamos algo dentro de ella, ya que generalmente es más fácil buscar algo en una colección ordenada, en lugar de una sin clasificar, ya que puede hacer conjeturas informadas e imponer suposiciones sobre los datos.

Hay muchos algoritmos que pueden clasificar elementos de manera eficiente, pero en esta guía veremos cómo implementar Conteo de clasificación en Java.

Clasificación por conteo en Java

Counting Sort es un algoritmo de clasificación estable y no comparativo, y su uso principal es para clasificar matrices de enteros no negativos.

Counting Sort cuenta el número de objetos que tienen distintos valores clave y luego aplica una suma de prefijo en esos recuentos para determinar la posición de cada clave en la salida. Al igual que todos los demás algoritmos de clasificación no comparativos, Counting Sort también realiza la clasificación sin ninguna comparación entre los elementos que se van a clasificar. Además, al ser un algoritmo de clasificación estable, Counting Sort conserva el orden de los elementos con claves iguales ordenados en la matriz de salida tal como estaban en la matriz original.

Esta operación da como resultado, esencialmente, una lista de ocurrencias de enteros, que normalmente llamamos arreglo de conteo. Counting Sort usa el arreglo de conteo auxiliar para determinar las posiciones de los elementos:

img

Cada índice en la matriz de conteo representa un elemento en la matriz de entrada. El valor asociado con este índice es el número de ocurrencias (el conteo) del elemento en la matriz de entrada.

La mejor manera de tener una idea de cómo funciona Counting Sort es ver un ejemplo. Consideremos que tenemos una matriz:

1
int[] arr = {0, 8, 4, 7, 9, 1, 1, 7};

En aras de la simplicidad, los elementos de la matriz solo serán de un solo dígito, es decir, números del 0 al 9. Dado que el valor más grande que podemos tener es 9, etiquetemos el valor máximo como max = 9.

Esto es importante porque necesitaremos designar una nueva matriz de conteo, que consta de elementos max + 1. Esta matriz se usará para contar el número de ocurrencias de cada dígito dentro de nuestra matriz original que se nos da para ordenar, por lo que debemos inicializar toda la matriz de conteo a 0, es decir:

1
int[] countArray = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

Dado que hay 10 elementos posibles que puede tener nuestra matriz, hay diez ceros para cada dígito.

Dado que hemos definido la matriz en la que trabajaremos, y también hemos definido nuestra matriz de conteo para llevar la cuenta de cada aparición de un dígito, debemos realizar el siguiente paso para que funcione la ordenación por conteo:

Paso 1:

Recorriendo toda nuestra matriz arr en un solo ciclo for, para cada i desde 0 hasta n-1, donde n es el número de elementos en arr, Contaremos la ocurrencia de cada dígito incrementando el valor en la posición arr[i] en nuestro countArray. Veamos eso en código:

1
2
for(int i = 0; i < arr.length; i++)
    countArray[arr[i]]++;

Después del primer paso, nuestro countArray se ve así: [1, 2, 0, 0, 1, 0, 0, 2, 1, 1].

Paso 2:

Como ahora tenemos nuestro countArray lleno de valores, pasamos al siguiente paso: aplicar sumas de prefijos al countArray. Las sumas de prefijos se forman básicamente cuando agregamos cada uno de los números anteriores en la matriz al siguiente de forma acumulativa, formando una suma de todos los prefijos vistos hasta ahora:

1
2
for(int i=1; i < countArray.length; i++)
    countArray[i] += countArray[i-1];

Y después de aplicar este paso obtenemos el siguiente countArray: [1, 3, 3, 3, 4, 4, 4, 6, 7, 8].

Paso 3:

El tercer y último paso es calcular las posiciones de los elementos en la salida ordenada en función de los valores en countArray. Para este propósito, necesitaremos una nueva matriz que llamaremos outputArray. El tamaño de outputArray es el mismo que nuestro arr original, y una vez más inicializamos esta matriz a todos ceros:

1
int[] outputArray = {0, 0, 0, 0, 0, 0, 0, 0};

Como mencionamos anteriormente, Counting Sort es una clasificación estable. Si iteramos a través de nuestra matriz arr de 0 a n-1, podemos terminar cambiando los elementos y arruinando la estabilidad de este algoritmo de clasificación, por lo que iteramos la matriz en el orden inverso.

Encontraremos el índice en nuestro countArray que es igual al valor del elemento actual arr[i]. Luego, en la posición countArray[arr[i]] - 1 colocaremos el elemento arr[i]. Esto garantiza que mantengamos la estabilidad de este tipo. Luego, decrementamos el valor countArray[i] en uno, y continuamos haciendo lo mismo hasta i >= 0:

1
2
3
4
for(int i = arr.length-1; i >= 0; i--){
    outputArray[countArray[arr[i]] - 1] = arr[i];
    countArray[arr[i]]--;
}

Al final del algoritmo, podemos simplemente copiar los valores de outputArr en nuestra matriz inicial arr e imprimir la matriz ordenada:

1
2
3
4
for(int i = 0; i < arr.length; i++){
    arr[i] = outputArray[i];
    System.out.print(arr[i] + " ");
}

La ejecución, por supuesto, nos da la matriz ordenada con estabilidad garantizada (orden relativo) de elementos iguales:

1
0 1 1 4 7 7 8 9

Complejidad del tipo de conteo

Discutamos la complejidad de tiempo y espacio de Counting Sort.

Digamos que n es el número de elementos en la matriz arr, y k es el rango de valores permitidos para esos n elementos de 1...n. Como estamos trabajando solo con bucles for simples, sin llamadas recursivas, podemos analizar la complejidad del tiempo de la siguiente manera:

  • Contar la ocurrencia de cada elemento en nuestro rango de entrada toma tiempo O (n),
  • Calcular las sumas de los prefijos toma tiempo O(k),
  • Y calcular el outputArray basado en los dos anteriores toma tiempo O(n).

Teniendo en cuenta todas las complejidades de estos pasos individuales, la complejidad temporal de Counting Sort es O(n+k), lo que hace que el caso promedio de Counting Sort sea lineal, lo que es mejor que la mayoría de los algoritmos de clasificación basados ​​en comparación. Sin embargo, si el rango de k es 1...n², el peor caso de Counting Sorts se deteriora rápidamente a O(n²) que es realmente malo.

Afortunadamente, esto no sucede a menudo, y existe una manera de garantizar que nunca suceda. Así es como surgió Radix Sort, que generalmente usa Counting Sort como su subrutina principal durante la clasificación.

Al emplear Ordenar por conteo en múltiples subarreglos acotados, la complejidad del tiempo nunca se deteriora a O(n²). Además, Radix Sort puede usar cualquier algoritmo estable y no comparativo en lugar de Counting Sort, pero es el más utilizado.

If you'd like to read more about Radix Sort, read our Clasificación Radix en Java!

Por otro lado, el problema de la complejidad del espacio es mucho más fácil. Dado que nuestro countArray de tamaño k es más grande que nuestro conjunto inicial de n elementos, la complejidad dominante allí será O(k). Lo importante a tener en cuenta es que, cuanto mayor sea el rango de elementos en la matriz dada, mayor será la complejidad espacial de Counting Sort.

Conclusión

En este artículo hemos descrito qué es Counting Sort, cómo funciona y cómo implementarlo en Java.

Aunque Counting Sort se queda corto en comparación con muchos otros algoritmos de clasificación (ordenar solo números enteros, tener una mayor complejidad espacial potencial, etc.), tiene algunas ventajas, la principal es que Counting Sort se usa como una subrutina para otros algoritmos de clasificación más poderosos, como Radix Sort, y dominarlo es crucial para implementar Radix Sort (que principalmente solo segrega y delega subarreglos a su los a su