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

typedef struct lista {
    int num;
    struct lista *prox;
} lista;

void radix_sort(int *, int);
void insere(lista **, int);
int pop(lista **);
void imprime(int *vetor, int tamanho);

int main()
{
    int tamanho = 20;
    int vetor[tamanho];
    int i;
    
    srand(time(NULL));
    for(i = 0; i < tamanho; i++) {
        vetor[i] = rand() % tamanho;
    }
    
    imprime(vetor, tamanho);
    printf("\n");
    
    radix_sort(vetor, tamanho);
    
    imprime(vetor, tamanho);
    printf("\n");
    
    return 0;
}

void insere(lista **l, int valor)
{
    lista *aux = *l;

    if(*l == NULL) {
        *l = (lista *)malloc(sizeof(lista));
        (*l)->num = valor;
        (*l)->prox = NULL;
    } else {
        while(aux->prox != NULL) aux = aux->prox;
        aux->prox = (lista *)malloc(sizeof(lista));
        aux = aux->prox;
        aux->num = valor;
        aux->prox = NULL;
    }
}

int pop(lista **l)
{
    int ret;
    lista *aux;
    
    ret = (*l)->num;
    aux = *l;
    *l = (*l)->prox;
    free(aux);
    
    return ret;
}

void radix_sort(int *vetor, int tamanho)
{

    lista *bucket1 = NULL;
    lista *bucket2 = NULL;
    int i, j;
    int numero_bits;
    
    numero_bits = sizeof(int) * 8;
    
    for(i = 0; i < numero_bits; i++) {
        for(j = 0; j < tamanho; j++) {
            if((((vetor[j] >> i) & 0xf) % 2) == 0)
                insere(&bucket1, vetor[j]);
            else
                insere(&bucket2, vetor[j]);
        }
        
        j = 0;
        while(bucket1 != NULL) {
            vetor[j] = pop(&bucket1);
            j++;
        }
        
        
        while(bucket2 != NULL) {
            vetor[j] = pop(&bucket2);
            j++;
        }
        
    }
    
}

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