Ordenamiento por conteo

Count Sort (ordenamiento por conteo) es un algoritmo de ordenamiento que puede ser implementado de manera secuencial en Java como se muestra a continuación:

public static void sequentialCountSort(int a[]) {
    final int n = a.length;
    final int[] temp = new int[n];
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (a[j] < a[i]) {
                count++;
            } else if (a[i] == a[j] && j < i) {
                count++;
            }
        }
        temp[count] = a[i];
    }
    System.arraycopy(temp, 0, a, 0, n);
}

Para cada elemento a[i] del arreglo a, contamos el número de elementos del arreglo que son menores a a[i]. Posteriormente insertamos a[i] a un arreglo temporal usando como índice el resultado del conteo correspondiente. Solo hay un pequeño detalle que cuidar, ya que si hay elementos repetidos en el arreglo a éstos ocuparían la misma localidad dentro del arreglo temporal. Pare evitar este problema, el código incrementa el contador para elementos iguales en base a sus índices. Es decir, si a[i] == a[j] y j < i, entonces consideramos a a[j] como “menor que” a[i].

Una vez que concluye el algoritmo, sobre-escribimos el arreglo original con el contenido del arreglo temporal usando el método System.arraycopy().

Reference: [PACHECO] pp. 267 y 268.

Programación multinúcleo

Ordenamiento por conteo