// Binary Radix Sort
#include<stdio.h>
#include<math.h>
int print_arr(int arr[], int n)
{
int z;
for(z=0 ; z<n ; z++)
{
printf("%d ", arr[z]);
}
printf("\n");
}
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void BinaryRadixSort(int arr[], int arr_size)
{
int biggest_int_len = log2(getMax(arr, arr_size))+1;
int i;
int digit;
for(i=1 ; i<=biggest_int_len ; i++)
{
digit=i;
int j;
int bit;
int pos=0;
int min=-1;
int min2=-1;
int min_val;
for(j=0 ; j<arr_size ; j++)
{
int len=(int) (log2(arr[j])+1);
if(i>len)
{
bit=0;
}
else
{
bit=(arr[j] & (1 << (digit - 1)));
}
if(bit==0)
{
min_val=arr[j];
min=j;
min2=j;
break;
}
}
while(min!=-1)
{
while(min>pos)
{
arr[min]=arr[min-1];
min--;
}
arr[pos]=min_val;
pos++;
int k;
min=-1;
for(k=min2+1 ; k<arr_size ; k++)
{
int len=(int) (log2(arr[k])+1);
if(i>len)
{
bit=0;
}
else
{
bit= arr[k] & (1 << (digit-1));
}
if(bit==0)
{
min_val=arr[k];
min=k;
min2=k;
break;
}
}
}
}
}
int main()
{
int arr[16]={10,43,73,14,64,2,6,1,5,3,6,3,5,8,4,5};
int size=16;
BinaryRadixSort(arr, size);
printf("\n--------------------------\n");
print_arr(arr, size);
return 0;
}
