#include <cstdio>

void sort1_k(int * A, int n, int k){
//    int ocurrencias[k+1]={0}; //forma alternativa, pero mejor utilizar el for para entender bien el orden
    int ocurrencias[k+1]; // no usamos el primer lugar 
    // se hace k veces algo cte -> O(k)
    for (int i=0; i<k+1;i++){ // inicializamos el indice 0 aunque no se use
        ocurrencias[i]=0;
    }
     // se hace n veces algo cte -> O(n)
    for(int j=0;j<n;j++){
        ocurrencias[A[j]]++;
    }
    int actual=0;
     // se hace n veces (es fácil verlo con actual++ que llega hasta n) -> O(n)
     // se suman las ocurrencias 
    for(int l=1; l<k+1;l++){
        for (int t=0; t<ocurrencias[l];t++){
            A[actual]=l;
            actual++;
        }
    }
    
}

int main()
{
    int A[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = 11;
    int k = 10;

    printf("Arreglo original:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");

    sort1_k(A, n, k);

    printf("Arreglo ordenado:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", A[i]);
    }
    printf("\n");

    return 0;
}