Skip to content

Instantly share code, notes, and snippets.

@aycabta
Last active December 19, 2015 04:59
Embed
What would you like to do?
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
extern void bitsort_recursive(unsigned int *old_seq, unsigned int *new_seq, size_t size, size_t maxbit);
void bitsort_recursive(unsigned int *old_seq, unsigned int *new_seq, size_t size, size_t maxbit)
{
int i;
size_t l_pos;
size_t r_pos;
int t;
maxbit -= 1;
if (maxbit) {
t = 1 << maxbit;
l_pos = 0;
r_pos = size - 1;
for (i = 0; i < size; ++i) {
if (old_seq[i] & t) {
new_seq[r_pos] = old_seq[i];
r_pos--;
} else {
new_seq[l_pos] = old_seq[i];
l_pos++;
}
}
if (l_pos > 0) {
bitsort_recursive(new_seq, old_seq, l_pos, maxbit); /* left */
}
if (size - l_pos > 0) {
bitsort_recursive(new_seq + l_pos, old_seq + l_pos, size - l_pos, maxbit); /* right */
}
}
}
void bitsort(unsigned int *seq, size_t size, size_t maxbit)
{
int i;
unsigned int *old_seq;
unsigned int *new_seq;
old_seq = (unsigned int*)malloc(sizeof(unsigned int) * size);
new_seq = (unsigned int*)malloc(sizeof(unsigned int) * size);
memcpy(old_seq, seq, sizeof(unsigned int) * size);
bitsort_recursive(old_seq, new_seq, size, maxbit);
if (maxbit % 2 == 1) {
for (i = 0; i < size; ++i) {
printf("%u\n", old_seq[i]);
}
} else {
for (i = 0; i < size; ++i) {
printf("%u\n", new_seq[i]);
}
}
free(old_seq);
free(new_seq);
}
int main(void)
{
unsigned int list[] = {3, 1, 4, 15, 9, 255, 254, 128, 127, 89, 7, 9};
bitsort(list, sizeof(list) / sizeof(unsigned int), sizeof(unsigned int) * 8);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment