Programa en C para ordenar por conteo

La clasificación por conteo es una técnica de clasificación basada en claves entre un rango específico. Funciona contando la cantidad de objetos que tienen valores clave distintos (tipo de hashing). Luego, haga algo de aritmética para calcular la posición de cada objeto en la secuencia de salida. 

Algoritmo:

Paso 1: Iniciar
Paso 2: Buscar los datos más grandes de la array.
Paso 3: establezca el valor de todos los elementos de la array en 0.
Paso 4: aumente los datos de conteo de cada número que se encuentra en la array.
Paso 5: Encuentre la frecuencia acumulada
Paso 6: Almacene el número en la array de salida.
Paso 7: Imprima la array de salida
Paso 8: Deténgase.

Pseudocódigo:

COUNTINGSORT(A)
   FOR I = 0 TO K DO
      C[I] = 0
   FOR J = 0 TO N DO
      C[A[J]] = C[A[J]] + 1
   FOR I = 1 TO K DO
      C[I] = C[I] + C[I-1]
    FOR J = N-1 TO 0 DO
      B[ C[A[J]]-1 ] = A[J]
      C[A[J]] = C[A[J]] - 1
END FUNCTION

// C Program for counting sort
#include <stdio.h>
#include <string.h>
#define RANGE 255
 
// The main function that sort the given string arr[] in
// alphabetical order
void countSort(char arr[])
{
    // The output character array that will have sorted arr
    char output[strlen(arr)];
 
    // Create a count array to store count of individual
    // characters and initialize count array as 0
    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));
 
    // Store count of each character
    for(i = 0; arr[i]; ++i)
        ++count[arr[i]];
 
    // Change count[i] so that count[i] now contains actual
    // position of this character in output array
    for (i = 1; i <= RANGE; ++i)
        count[i] += count[i-1];
 
    // Build the output character array
    for (i = 0; arr[i]; ++i)
    {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }
 
    // Copy the output array to arr, so that arr now
    // contains sorted characters
    for (i = 0; arr[i]; ++i)
        arr[i] = output[i];
}
 
// Driver program to test above function
int main()
{
    char arr[] = "geeksforgeeks";//"applepp";
 
    countSort(arr);
 
    printf("Sorted character array is %sn", arr);
    return 0;
}

Sorted character array is eeeefggkkorssn

Análisis de complejidad de tiempo 
Peor caso
cuando los datos están sesgados y el rango es grande Entonces la complejidad de tiempo es O(N+K)
Mejor caso
cuando todos los elementos son iguales La complejidad de tiempo es O(N+K)
Caso
promedio La complejidad de tiempo promedio es O(N+K) )

Complejidad espacial: 

LA COMPLEJIDAD DEL ESPACIO PARA ESTE TIPO ES O(K).

ventajas :

1. Count Sort Process Rápido en menos tiempo.
2.  Es útil para conjuntos de datos de tamaño pequeño.
    

Desventajas 

1. No es útil Big Data.
2. No es útil para ordenar valores de string.
3. No es un algoritmo de clasificación en el lugar
4.  Requiere espacio adicional adicional para la operación de clasificación. como bien (k)
    

¡ Consulte el artículo completo sobre clasificación por conteo para obtener más detalles!