#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

void radix_sort(int *, int, int);
void imprime(int *vetor, int tamanho);

int main(int argc, char **argv)
{
    int tamanho;
    int *vetor;
    int i;
    int maior = 0;
    clock_t inicio, fim;
    float periodo;
    
	if(argc < 2) {
		printf("Use: %s numero\n", argv[0]);
		return -1;
	}
	
	tamanho = atoi(argv[1]);

    vetor = (int *)malloc(sizeof(int)*tamanho);
    
    srand(time(NULL));
    for(i = 0; i < tamanho; i++) {
        vetor[i] = (rand() % 1022)+1;
        if(vetor[i] > maior)
            maior = vetor[i];
    }
    
    //imprime(vetor, tamanho);
    //printf("\n");
    
    inicio = clock();
    radix_sort(vetor, tamanho, maior);
    fim = clock();
    periodo = (float)(((float)fim-(float)inicio)/CLOCKS_PER_SEC);
    
    printf("Tempo: %.15f\n", periodo);
    //imprime(vetor, tamanho);
    //printf("\n");
    
    return 0;
}

void radix_sort(int *vetor, int tamanho, int maior)
{

    int i, j, k, l;
    int numero_bits;
    
    int **temp;

    temp = (int **)malloc(sizeof(int *)*2);
    temp[0] = (int *)malloc(sizeof(int)*tamanho);
    temp[1] = (int *)malloc(sizeof(int)*tamanho);

    numero_bits = (log(maior)/log(2))+1;
    
    for(i = 0; i < numero_bits; i++) {
        k = 0;
        l = 0;

        for(j = 0; j < tamanho; j++) {
            if((((vetor[j] >> i) & 0xf) % 2) == 0) {
                temp[0][k++] = vetor[j];
            } else {
                temp[1][l++] = vetor[j];
            }
        }
        
        temp[0][k] = '0';
        temp[1][l] = '0';
        
        j = 0;
        while(temp[0][j] != '0') {
            vetor[j] = temp[0][j];
            j++;
        }
        
        k=0;
        while(temp[1][k] != '0') {
            vetor[j] = temp[1][k];
            j++;
            k++;
        }
            
    }
}

void imprime(int *vetor, int tamanho)
{
    int i;
    
    for(i = 0; i < tamanho; i++)
        printf("%d ", vetor[i]);
}