c - Implementing American Flag Sort for Integers (sorts by byte & includes negative values) -
the american flag sort in-place variant of radix sort, implement in c both positive , negative integers. this java implementation used basis. similar 1 written here.
converting algorithm msd (most significant digit) msb (most significant byte) seems trickier thought. inputs of size 10, appears work enough, trying sort 100 elements crashes program.
this code far:
#include <limits.h> #include "americanflagsort.h" #define buckets 256 #define mask 255 #define flip_int(x) ((x)^((0-((x) >> 31) ) | 0x80000000)) // bitwise modulo: n % 256 == n & 255 #define find_bucket(x, y) (((x) >> (char_bit*y)) & mask) static void sort(int *array, size_t start, size_t num, int bytepos) { // first pass: find counts int count[buckets] = { 0 }; int offset[buckets] = { 0 }; for(int = 0; < num; ++i) { ++count[find_bucket(flip_int(array[i]), bytepos)]; } offset[0] = start; for(int = 1; < buckets; ++i) { offset[i] = count[i-1]+offset[i-1]; } for(int = 0; < buckets; ++i) { while(count[i] > 0) { int origin = offset[i]; int = origin; int n = array[from]; array[from] = -1; { int bucket = find_bucket(flip_int(n), bytepos); int = offset[bucket]++; --count[bucket]; int tmp = array[to]; array[to] = n; n = tmp; = to; } while(from != origin); } } if(bytepos > 0) { for(int = 0; < buckets; ++i) { int begin = (i > 0) ? offset[i-1] : start; int end = offset[i]; if(end-begin > 1) { sort(array, begin, end, bytepos-1); } } } } void americanflagsort(int *array, size_t num) { sort(array, 0, num, sizeof(int)-1); }
in particular, snippet int = offset[bucket]++;
causes me trouble. to
used subscript access array , keeps incrementing, leads out of bound place program has no business being at.
how make work?
Comments
Post a Comment