Radix Sort Help

[Foodbank]

Hi everyone,

I'm having trouble implementing a supposedly simple Least Significant
Digit first Radix Sort. The book I'm using gave me somewhat of a
template that I touched up (below), but I'm very unsure of where to
start. I know the basic layout (Initialization of memory space,
Distribution of numbers in bins, and then Collection of the bins), but
I don't know how to code it. The examples I've seen don't pertain to my
situation enough to help me. Any help is greatly appreciated.

Thanks,
James

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
void lsd_radix_sort(unsigned int *, int);

main(int argc, char *argv[]) {
        int i, nvals = 10000;
        unsigned int *array;
        if(argc > 1)
                nvals = atoi(argv[1]);
        array = malloc(nvals * sizeof(unsigned int));
        for(i = 0; i < nvals; i++)
                array[i] = rand();
        lsd_radix_sort(array, nvals);
}



#define	BITS	8
#define	RADIX	(1<<BITS)
#define	DIGITS	(32/BITS)
void lsd_radix_sort(unsigned int *array, int n) {
	int i, j, k, d, shift;
	int *bin[RADIX], n_in_bin[RADIX], size_bin[RADIX];
	unsigned int v;

/insertion of least significant digit first code below ***** */
	

}

 

[Arctic Fidelity]

Hi everyone,

I'm having trouble implementing a supposedly simple Least Significant
Digit first Radix Sort. The book I'm using gave me somewhat of a
template that I touched up (below), but I'm very unsure of where to
start. I know the basic layout (Initialization of memory space,
Distribution of numbers in bins, and then Collection of the bins), but
I don't know how to code it. The examples I've seen don't pertain to my
situation enough to help me. Any help is greatly appreciated.

I've been trying to email my answers to you, but yahoo is a terrible pain
to get mail through. Always bouncing stuff. :-/ At any rate, I feel
like I would like to have my code ripped to shreds anyways, so I'll just
post it here as well, and see what people say:

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

int maxdigs;

struct llst {
int n;
struct llst *cdr;
};

void llstFree(struct llst *a)
{
struct llst *b;

if (a != NULL) {
do {
b = a;
a = a->cdr;
free(b);
} while (a != NULL);
}
}

int getDig(int n, int digit)
{
int x;
char c[2];
char *buf = malloc(maxdigs + 1);
if (buf == NULL) {
fprintf(stderr, "Insufficient Memory.\n");
exit(EXIT_FAILURE);
}
sprintf(buf, "%d", n);
c[0] = buf[digit - 1];
c[1] = '\0';
x = strtol(c, NULL, 10);
free(buf);
return x;
}

void append(struct llst **list, int num)
{
struct llst *l2;
struct llst *l3;

l2 = malloc(sizeof(struct llst));
if (l2 == NULL) {
fprintf(stderr, "Insufficient Memory.\n");
exit(EXIT_FAILURE);
}

l2->n = num;
l2->cdr = NULL;

if (*list == NULL) {
*list = l2;
} else {
l3 = *list;
while (l3->cdr != NULL) {
l3 = l3->cdr;
}
l3->cdr = l2;
}
}

struct llst *divide(struct llst *list, int digit)
{
int i;
struct llst *l2;
struct llst *l3;

/* Create bins */
struct llst *a[10];
for (i = 0; i < 10; ++i) {
a = NULL;
}

/* LOOP: Read numbers and sort */
l2 = list;
while (l2 != NULL) {
switch (getDig(l2->n, digit)) {
case 0: append(&a[0], l2->n); break;
case 1: append(&a[1], l2->n); break;
case 2: append(&a[2], l2->n); break;
case 3: append(&a[3], l2->n); break;
case 4: append(&a[4], l2->n); break;
case 5: append(&a[5], l2->n); break;
case 6: append(&a[6], l2->n); break;
case 7: append(&a[7], l2->n); break;
case 8: append(&a[8], l2->n); break;
case 9: append(&a[9], l2->n); break;
}
l2 = l2->cdr;
}

/* Recombine bins */
l2 = list;
i = 0;
do {
l3 = a;
while (l3 != NULL) {
l2->n = l3->n;
l2 = l2->cdr;
l3 = l3->cdr;
}
++i;
} while (i < 10);

for (i = 0; i < 10; ++i) {
llstFree(a);
}
return list;
}

struct llst *rdxsort(struct llst *list, int digits)
{
while (digits > 0) {
list = divide(list, digits);
--digits;
}

return list;
}

int main(int argc, char *argv[])
{
struct llst *list = NULL;
struct llst *l2 = NULL;
char *buf;
FILE *ifile;
char c;
int i;

if (argc != 3) {
fprintf(stderr, "Invalid arguments.\n");
return EXIT_FAILURE;
}

maxdigs = strtol(argv[1], NULL, 10);
buf = malloc(maxdigs + 1);
ifile = fopen(argv[2], "r");

c = fgetc(ifile);
i = 0;
while (c != EOF) {
if (c == '\n') {
buf = '\0';
append(&list, strtol(buf, NULL, 10));
i = 0;
} else {
buf[i++] = c;
}
c = fgetc(ifile);
}

printf("Unsorted: \n");
l2 = list;
while (l2 != NULL) {
printf("%d\n", l2->n);
l2 = l2->cdr;
}

list = rdxsort(list, maxdigs);

printf("Sorted:\n");
l2 = list;
while (l2 != NULL) {
printf("%d\n", l2->n);
l2 = l2->cdr;
}

llstFree(list);
free(buf);
return 0;
}

- Arctic

 

[Thad Smith]

Hi everyone,

I'm having trouble implementing a supposedly simple Least Significant
Digit first Radix Sort. The book I'm using gave me somewhat of a
template that I touched up (below), but I'm very unsure of where to
start. I know the basic layout (Initialization of memory space,
Distribution of numbers in bins, and then Collection of the bins), but
I don't know how to code it. The examples I've seen don't pertain to my
situation enough to help me. Any help is greatly appreciated. ....
#define BITS 8
#define RADIX (1<<BITS)
#define DIGITS (32/BITS)
void lsd_radix_sort(unsigned int *array, int n) {
int i, j, k, d, shift;
int *bin[RADIX], n_in_bin[RADIX], size_bin[RADIX];
unsigned int v;

/insertion of least significant digit first code below ***** */


}

I'll just post it here as well, and see what people say:

int getDig(int n, int digit)
{
int x;
char c[2];
char *buf = malloc(maxdigs + 1);
if (buf == NULL) {
fprintf(stderr, "Insufficient Memory.\n");
exit(EXIT_FAILURE);
}
sprintf(buf, "%d", n);
c[0] = buf[digit - 1];
c[1] = '\0';
x = strtol(c, NULL, 10);
free(buf);
return x;
}

This version of getDig is very inefficient and, worse, doesn't work when
the number of decimal digits vary in the list of numbers. The format %d
will convert the number left justified, while we need to process the
numbers starting with the rightmost digit. It also misses the point of
Foodbank's code that I quoted above that he wants to use a radix of 256
not 10. This radix would make the program more efficient (fewer passes)
and easier to extract the digits.

void append(struct llst **list, int num)
{
struct llst *l2;
struct llst *l3;

l2 = malloc(sizeof(struct llst));
if (l2 == NULL) {
fprintf(stderr, "Insufficient Memory.\n");
exit(EXIT_FAILURE);
}

l2->n = num;
l2->cdr = NULL;

if (*list == NULL) {
*list = l2;
} else {
l3 = *list;
while (l3->cdr != NULL) {
l3 = l3->cdr;
}
l3->cdr = l2;
}
}

Wow. You are running the whole list to find the tail each time you add
another member. It would be much better to use a tail pointer. Also if
you are going to put each number in a list, it would be much more
efficient to move each element containing the number, rather than pass
the number, allocate another structure, initialize it, then free up the
extra copies for each pass.

struct llst *divide(struct llst *list, int digit)
{
int i;
struct llst *l2;
struct llst *l3;

/* Create bins */
struct llst *a[10];
for (i = 0; i < 10; ++i) {
a = NULL;
}

/* LOOP: Read numbers and sort */
l2 = list;
while (l2 != NULL) {
switch (getDig(l2->n, digit)) {
case 0: append(&a[0], l2->n); break;
case 1: append(&a[1], l2->n); break;
case 2: append(&a[2], l2->n); break;
case 3: append(&a[3], l2->n); break;
case 4: append(&a[4], l2->n); break;
case 5: append(&a[5], l2->n); break;
case 6: append(&a[6], l2->n); break;
case 7: append(&a[7], l2->n); break;
case 8: append(&a[8], l2->n); break;
case 9: append(&a[9], l2->n); break;
}
l2 = l2->cdr;
}

/* Recombine bins */
l2 = list;
i = 0;
do {
l3 = a;
while (l3 != NULL) {
l2->n = l3->n;
l2 = l2->cdr;
l3 = l3->cdr;
}
++i;
} while (i < 10);

for (i = 0; i < 10; ++i) {
llstFree(a);
}
return list;
}

struct llst *rdxsort(struct llst *list, int digits)
{
while (digits > 0) {
list = divide(list, digits);
--digits;
}

return list;
}

int main(int argc, char *argv[])
{
struct llst *list = NULL;
struct llst *l2 = NULL;
char *buf;
FILE *ifile;
char c;
int i;

if (argc != 3) {
fprintf(stderr, "Invalid arguments.\n");
return EXIT_FAILURE;
}

maxdigs = strtol(argv[1], NULL, 10);
buf = malloc(maxdigs + 1);
ifile = fopen(argv[2], "r");

c = fgetc(ifile);
i = 0;
while (c != EOF) {
if (c == '\n') {
buf = '\0';
append(&list, strtol(buf, NULL, 10));
i = 0;
} else {
buf[i++] = c;
}
c = fgetc(ifile);
}

printf("Unsorted: \n");
l2 = list;
while (l2 != NULL) {
printf("%d\n", l2->n);
l2 = l2->cdr;
}

list = rdxsort(list, maxdigs);

printf("Sorted:\n");
l2 = list;
while (l2 != NULL) {
printf("%d\n", l2->n);
l2 = l2->cdr;
}

llstFree(list);
free(buf);
return 0;
}

The number of digits (passes) needed is determined by the number of
digits in the maximum number to be sorted. You shouldn't need to read
it separately. Actually, reading it separately is both extra work and
an opportunity for error.