bucketsort

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

#define max 1000

void bucket_sort(int v[],int tam);
void bubble(int v[],int tam);
int countSetBits(int n);

int countSetBits(int n)
{
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

void bucket_sort(int v[], int tam){

	int i, j, k;

	typedef struct {
        int topo;
        int balde[tam];
	}bucket;

	bucket b[9];  //Como a entrada máxima é 1000, o número de bits 1 é 9 (111111111 na base 2 = 511 na base 10)

	for(i = 0; i < 9; i++)
        b[i].topo = 0;

	for(i = 0; i < tam; i++){
        j = countSetBits(v[i]);			//"countSetBits() verifica quantos bits tem o valor da posição "i" do vetor "v" e atribui esse valor em "j".
        b[j].balde[b[j].topo] = v[i];	//O valor de j é posto na posição j do vetor bucket "b", que representa o balde com a quantidade de bits j.
        (b[j].topo)++;					//O topo da posição j do balde é atualizado.

    }

	for(i = 0; i < 9; i++)                    //Cada balde é ordenado com o bubblesort, uma vez que, teoricamente, são poucos elementos e distam muito pouco em módulo
        if(b[i].topo)					     //um do outro.
            bubble(b[i].balde, b[i].topo);

    for ( i = 0; i < 9; i++) {
    	for ( j = 0; j < b[i].topo; j++)	//Todos os elementos dos baldes (caso topo não seja igual a 0) são impressos.
    		printf("%d ", b[i].balde[j]);
    	if ( b[i].topo != 0 && i != tam)
			printf("\n");
	}

    i=0;

	for(j = 0; j < 9; j++){                    //O vetor v recebe o conteúdo dos baldes, que representam 0 até 9 bits 1, caso o balde não esteja vazio.
        for(k = 0; k < b[j].topo; k++){
            v[i] = b[j].balde[k];
            i++;
        }
    }

    bubble(v, tam);	/*Como nesse caso, para um bucket de x bits, pode conter números que diferem consideravelmente em módulo
    				(por exemplo, tanto o número 1 quanto o número 64 possuem o bit 1 uma vez apenas) a função do bubble sorte é chamada ao final
					da concatenação dos buckets, uma vez que o vetor está praticamente já ordenado.*/
}

void bubble(int v[],int tam){
	int i,j,temp,flag;
    if(tam)
    	for(j=0;j<tam-1;j++){
            flag=0;
            for(i=0;i<tam-1;i++){
                if(v[i+1]<v[i]){
                    temp=v[i];
                    v[i]=v[i+1];
                    v[i+1]=temp;
       	            flag=1;
         	    }
            }
      		if(!flag)
         		break;
        }
}



void imprimir_vetor(int *v, int n) {
	int i;
	for (i = 0; i < n; i++) {
		printf("%d ", v[i]);
	}
}

int main() {
	int n, i;

	scanf("%d", &n);

	if (n > max)
		exit(1);

	int *x = (int*) malloc (n * sizeof(int));
	if (x == NULL) {
		printf("Memoria insuficiente para alocar o vetor de %d posicoes.\n", n);
		exit(1);
	}

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

	bucket_sort(x, n);

	imprimir_vetor(x, n);

	free(x);
}