Algoritmo Counting Sort explicación método ordenación implementación en java

[Martin1395]

Hola, agradecería que me ayudaran con el algoritmo Counting Sort. El problema a resolver es: ordenar n datos aleatorios. Y ordenarlos de menor a mayor.

Espero puedan ayudarme con este ejercicio, gracias.

[Kabuto]

Pues a ver... porque no es fácil de explicar el Counting Sort....

Counting Sort es un algoritmo de ordenación muy útil cuando se trata de valores numéricos.
Normalmente las ordenaciones se hacen comparando un valor con otro, a ver cuál es mayor o menor..
Esto es fácil de entender y aplicar, pero requiere muchos ciclos de computación y por mucho que se optimice el código, siempre se van a repetir comparaciones innecesarias, pero inevitables.

Counting Sort es más eficaz porque no hace comparaciones. Lo que hace es crear un arreglo que representa TODOS los valores posibles dentro de una secuencia YA ORDENADA.
Cada elemento del arreglo hará la función de contador.
La secuencia siempre ha de ser entre 0 y un valor límite, que se ha de conocer de antemano.
Luego coge la lista de valores SIN ORDENAR y hace un recuento de cuántas veces aparece un determinado valor.

De esta manera, en el arreglo de contadores ordenados, ya sabe qué valores de la lista sin ordenar aparecen, y cuántas veces.

No se entiende un pijo, ¿verdad? 


Vamos a probar de otra manera. Mira, este método sería el algoritmo de ordenación Counting Sort

Código: [Seleccionar]

private static void countingSort(int[] valores, int limite) {

//Creamos array de contadores
int[] contadores = new int[limite + 1];

//Recorremos valores y los contamos
//Cada valor nos dice que contador hemos de incrementar
//Si por ejemplo el valor es 1, hay que incrementar el contador [1], etc...
for (int valor: valores)
contadores[valor]++;

//Ordenamos el array de valores, según lo contado para cada valor
int indice = 0;
for (int i = 0; i < contadores.length; i++) {
while (0 < contadores[i]) {
valores[indice] = i;
indice++;
contadores[i]--;
}
}

}
Como mi explicación no se ha entendido, el código tampoco se va a entender.
Pero ahora vamos a intentar hacer una representación visual de cada línea de código de ese algoritmo.

Por ejemplo, tenemos esta lista SIN ORDENAR:

3, 2, 5, 1, 3, 5

Ya vemos que son valores entre 0 y 5(límite)

El algoritmo lo primero que va a hacer es crear un array de 6 contadores (limite + 1):

Código: [Seleccionar]

//Creamos array de contadores
int[] contadores = new int[limite + 1];Así que en memoria tendríamos algo como esto:


El siguiente paso del algoritmo es recorrer los valores sin ordenar, y para cada valor incrementar el contador correspondiente.
Es decir, el primer número de la lista es el 3
Pues el contador en posición [3] se incrementa en  +1

Luego viene el 2, pues incrementamos el contador [2]

Luego viene el 5, el 1, otra vez el 3 y otra vez el 5.

Pues tras incrementar todos los contadores correspondientes, el array ahora quedaría así:


¿Lo ves? En este array ya tenemos todo lo que necesitamos para recrear la lista anterior, pero ordenada.
Sabemos que no hay ningún 0 en la lista, ni tampoco ningún 4, porque sus contadores no se han incrementado.

Sabemos que hay un 1, un 2, dos 3 y dos 5.
Es decir, la lista ordenada sería:

1, 2, 3, 3, 5, 5

Se ha conseguido ordenar sin hacer ninguna comparación, tan solo usando contadores.

Ahora falta un último paso, modificar el array de los valores desordenados, colocando los valores de forma ordenada, a partir del array de contadores.

Código: [Seleccionar]

//Ordenamos el array de valores, según lo contado para cada valor
int indice = 0;
for (int i = 0; i < contadores.length; i++) {
while (0 < contadores[i]) {
valores[indice] = i;
indice++;
contadores[i]--;
}
}Esta parte del código es la que más cuesta entender.
El bucle for, utiliza la i para recorrer el array de contadores.
El bucle while, añade al array de valores, los nuevos valores ordenados, según lo que se ha contado en el contador al que apunta la i

Si en una posición no se ha contado nada (contadores[ i ] es igual a 0), como ocurre con el 0 y el 4 en este ejemplo, pues el bucle while no hace nada y se pasa al siguiente contador.

Cuando sí se ha contado algo en una posición, el bucle while se repite tantas veces como indique el valor de ese contador.
Y, usando un índice que vamos a incrementar manualmente, añade al array de valores, el valor que tenga la i del bucle for.
Y entonces decrementa el contador hasta que llegue a 0, para que el while termine y pasemos al siguiente contador.

Es decir, teniendo este array de contadores:


Para la posición [ 0 ], el contador es 0, el while no va a hacer nada.

En la posición [1], el contador es 1, así que el while va añadir un 1 a la lista de valores ordenados.
Decrementará este contador, alzando el valor 0 y por tanto el while termina

En la posición [2], se ha contado 1, así que se añadirá un 2.
De nuevo decrementa el contador, alcanzando 0, por lo que el while cierra su ciclo.

En [3], se han contado 2.
Se añadirá primero un 3 y se decrementa el contador. Ahora tiene valor 1, así que el while repite el ciclo agregando otro 3 a la lista de valores.
Se decrementa el contador y ahora sí alcanza valor 0, así que while se termina.

En [4], el contador es 0, así que el while no interviene y se pasa al siguiente contador.

En [5], se han contado 2. Así que se añadirá un 5 y luego otro 5 más hasta agotar el contador con sendos decrementos.



Y ya tendríamos la lista completa y ordenada.

Espero que haya quedado más o menos claro. Hay cosas que son simples, pero algo difíciles de explicar.

A continuación te dejo un programa completo para poner a prueba este algoritmo:

Código: [Seleccionar]

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class CountingSort {

public static void main(String[] args) {

Scanner teclado = new Scanner(System.in);

System.out.print("¿Cuántos valores quieres crear?: ");
int numV = teclado.nextInt();
System.out.println("Se crearán valores entre 0 y un límite que tú decides.");
System.out.print("Valor límite: ");
int limite = teclado.nextInt();

int[] valoresAzar = crearValores(numV, limite);

System.out.println("\nValores sin ordenar");
System.out.println(Arrays.toString(valoresAzar));

countingSort(valoresAzar, limite);

System.out.println("\nValores ordenados mediante algoritmo Counting Sort");
System.out.println(Arrays.toString(valoresAzar));

System.out.println("\n\t\tFIN DE PROGRAMA");
teclado.close();
}

private static int[] crearValores(int nV, int lmt) {

Random azar = new Random();

int[] v = new int[nV];
for (int i = 0; i < nV; i++)
v[i] = azar.nextInt(lmt+1);

return v;
}

private static void countingSort(int[] valores, int limite) {

//Creamos array de contadores
int[] contadores = new int[limite + 1];

//Recorremos valores y los contamos
//Cada valor nos dice que contador hemos de incrementar
//Si por ejemplo el valor es 1, hay que incrementar el contador [1], etc...
for (int valor: valores)
contadores[valor]++;

//Ordenamos el array de valores, según lo contado para cada valor
int indice = 0;
for (int i = 0; i < contadores.length; i++) {
while (0 < contadores[i]) {
valores[indice] = i;
indice++;
contadores[i]--;
}
}

}

}
Al ejecutarlo, en pantalla veremos que funciona correctamente:

¿Cuántos valores quieres crear?: 15
Se crearán valores entre 0 y un límite que tú decides.
Valor límite: 50

Valores sin ordenar
[45, 2, 29, 44, 34, 33, 34, 9, 24, 35, 42, 27, 37, 20, 30]

Valores ordenados mediante algoritmo Counting Sort
[2, 9, 20, 24, 27, 29, 30, 33, 34, 34, 35, 37, 42, 44, 45]

      FIN DE PROGRAMA

Si quedan dudas, vuelve a preguntar.
Un saludo.

[Martin1395]

Muy bien explicado. muchisimas gracias, me es de gran ayuda. saludos.