Counting Sort

Counting Sort fue propuesto por Harold H. Seward en 1.954. Es un algoritmo que sólo fue diseñado para ordenar números enteros sin necesidad de realizar comparaciones, utiliza un contador (casillero) para cada valor que aparece en el vector de entrada. En la actualidad puede ser adaptado tanto a números decimales como a caracteres con un coste importante. Tiene raíz común con Bucket, partiendo ambos del algoritmo del Casillero. Se suele utilizar como apoyo en la ordenación Radix y en otros algoritmos. Al igual que los algoritmos del Casillero y Bucket trabaja en tiempo lineal.

Rendimiento – Complejidad
Mejor caso Ω	Peor caso O	Media Θ	Espacio
$k$ = rango. (n+k)	(n+k)	(n + k)	–

 

La mayor limitación de este algoritmo la provoca el rango entre el menor y mayor de los valores de los elementos del vector. Al tener la necesidad de contar las apariciones de cada uno de los valores de los elementos, necesita un vector de salida del tamaño del rango. Un ejemplo: Supongamos que los 500 elementos que debemos ordenar tienen valores que van desde 1 a 100.000.000, para resolver la ordenación necesita crear una matriz auxiliar de 100.000.000 elementos, algo sin sentido. La ventaja es que se puede paralelizar, podemos dividir el vector de entrada en las partes que nos interese, ordenarlas individualmente y al finalizar las fusionamos.

 

Una forma de representación visual:

1. En el 1º paso se determina el rango y se crea el vector contador con una dimensión K = al valor máximo encontrado en los elementos del vector. Se cuentan las apariciones de cada valor en el vector de entrada y se incorporan en el índice coincidente del valor dentro del vector contador. Finalmente se recorre el vector contador sumándose los valores de los índices (anterior + actual) al actual.
2. El paso 2 es un bucle que comienza con el último elemento del vector de entrada y finaliza con el primero. De forma reiterada se toman los valores de los elementos (vector entrada) y se asocian con el índice del vector contador, se coloca el valor del vector de entrada en el índice del vector de salida indicado por el valor que contiene el índice del vector contador, después se resta 1 al valor contenido en el índice del vector contador.

_{? Pulsar sobre el gráfico para ampliar.}

 

 

Ejemplo: Implementación en lenguaje Java.

 

public static int [] Ordenacontando(int[] Vector) {
        int tamañoV = Vector.length;
        int mayor = Vector[0];
        int menor = Vector[0];
        for (int i = 1; i < tamañoV; i++) {
            if (Vector[i] > mayor)  mayor = Vector[i];
            if (Vector[i] < menor)  menor = Vector[i];
        }
        int rango = mayor - menor + 1;
        int[] Vcuenta = new int[rango];

        for (int i = 0; i < tamañoV; i++)
            Vcuenta[Vector[i] - menor]++;

        for (int i = 1; i < rango; i++)
            Vcuenta[i] += Vcuenta[i - 1];

        int j = 0;
        for (int i = 0; i < rango; i++)
            while (j < Vcuenta[i])
                Vector[j++] = i + menor;
        return Vector;
    }

 

Rendimiento.

Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.