#include <stdio.h>

extern "C" void radixsort(unsigned tab[], int n, int k);

void print_array(char *title, unsigned *array, size_t size);

int get_nth_bit(unsigned number, int n)
{
    return (number >> n) & static_cast<unsigned>(1);
}

void radix_sort_rec_c(unsigned *array, size_t size, int bit)
{
    int left_one_index = 0, right_zero_index = size - 1;

    if(size == 0)
        return;

    while(1)
    {
        while(left_one_index < size && !get_nth_bit(array[left_one_index], bit)) left_one_index++;
        while(right_zero_index >= 0 && get_nth_bit(array[right_zero_index], bit)) right_zero_index--;

        if(left_one_index >= right_zero_index)
            break;

        unsigned temp = array[left_one_index];
        array[left_one_index] = array[right_zero_index];
        array[right_zero_index] = temp;
    }

    if(bit == 0)
        return;

    radix_sort_rec_c(array, left_one_index, bit - 1);
    radix_sort_rec_c(array + left_one_index, size - left_one_index, bit - 1);
}

void radix_sort_c(unsigned *array, size_t size)
{
    radix_sort_rec_c(array, size, 31);
}

void print_array(char *title, unsigned *array, size_t size)
{
    printf("%s:\n", title);

    for(int i = 0; i < size; i++)
    {
        printf("%d ", array[i]);
    }

    printf("\n");
}

int main(int argc, char **argv)
{
    printf("Hello world!\n");

    printf("Radix sort\n");
    unsigned first_array[10] = {10, 213, 241, 14, 513, 23, 152, 0, 41, 52};
    size_t first_size = 10;

    print_array("Unsorted array", first_array, first_size);
    radixsort(first_array, first_size, 31);
    print_array("Sorted array", first_array, first_size);

    return 0;
}