/*BIT INDEX SORT DSC*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000

int busca_repetidos(int E[], int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (E[i] == E[j])
                return 0;
        }
    }
    return 1;
}

int cpdelante(unsigned int bit) {
    int i;
    int cont = 0;
    //Se contarán los ceros de la izquierda del 1 más significativo
    for (i = 0; i < 32; i++) {
        if ((bit & 1) == 1) //Si se encuentra un 1 más a la derecha
            cont = 0; //se contará de nuevo
        else
            cont++;
        bit = bit >> 1; //Se mueven los bits a la derecha
    }
    return cont;
}

void bit_index_dsc(int E[], int n) {

    unsigned int B[N] = {0};

    int ind = 0; //index (indice)
    int off = 0; //offset (desplazamiento))

    //Etapa de clasificacion
    int i;
    for (i = 0; i < N; i++) {
        ind = E[i] / 32;
        off = E[i] % 32;
        B[ind] |= B[i] | (1 << off);
    }

    //Etapa de recuperación
    int j;
    i = 0;
    for (j = (N - 1); j >= 0; j--) {
        while (B[j] > 0) {
            off = 31 - cpdelante(B[j]);
            E[i] = j * 32 + off;
            B[j] -= (1 << off);
            i++;
        }
    }
}

void imprime_ordenado(int E[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", E[i]);
    }
    printf("\n");
}

int main(int argc, char** argv) {
    int n = -1;
    clock_t begin, end;
    double time_spent;

    int E[N] = {0};

    //while (n) {
    printf("Ingrese el numero de datos del arreglo:\n");

    scanf("%d", &n);

    if (n > 0) {
        printf("Ingrese los valores a ordenar:\n");

        int i;
        for (i = 0; i < n; i++)
            scanf("%d", &E[i]);

        if (busca_repetidos(E, n)) {
            begin = clock();
            bit_index_dsc(E, n);
            end = clock();
            imprime_ordenado(E, n);
        } else
            printf("Hay valores repetidos\n");
    }
    time_spent = (double) (end - begin) / CLOCKS_PER_SEC;
    printf("%f\n", time_spent * 1000);
    //}
    return (EXIT_SUCCESS);
}