On Sat, 29 Oct 2005 16:43:54 -0400, Foodbank <v8********@yahoo.com> wrote:
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[i] = 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[i];
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[i]);
}
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[i] = '\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
--
Using Opera's revolutionary e-mail client:
http://www.opera.com/mail/