473,322 Members | 1,610 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

Radix Sort Help

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
Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <stdlib.h>
  4. void lsd_radix_sort(unsigned int *, int);
  5.  
  6. main(int argc, char *argv[]) {
  7. int i, nvals = 10000;
  8. unsigned int *array;
  9. if(argc > 1)
  10. nvals = atoi(argv[1]);
  11. array = malloc(nvals * sizeof(unsigned int));
  12. for(i = 0; i < nvals; i++)
  13. array[i] = rand();
  14. lsd_radix_sort(array, nvals);
  15. }
  16.  
  17.  
  18.  
  19. #define    BITS    8
  20. #define    RADIX    (1<<BITS)
  21. #define    DIGITS    (32/BITS)
  22. void lsd_radix_sort(unsigned int *array, int n) {
  23. int i, j, k, d, shift;
  24. int *bin[RADIX], n_in_bin[RADIX], size_bin[RADIX];
  25. unsigned int v;
  26.  
  27. /insertion of least significant digit first code below ***** */
  28.  
  29.  
  30. }
  31.  
Nov 15 '05 #1
2 2379
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/
Nov 15 '05 #2
Arctic Fidelity wrote:
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. .... #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[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;
}


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.

--
Thad

Nov 15 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

18
by: Kevin Doyle | last post by:
Hi I just found this macro. I want to convert a dword to string using this _ultoa but I don't understand the radix part of the function. what value of radix should I use so as not to effect the...
4
by: | last post by:
Hi, What libraries does C# have for UUEncoding a file? Thanks
7
by: Foodbank | last post by:
Hi everyone. I'm having trouble with this radix sorting program. I've gotten some of it coded except for the actual sorting :( The book I'm teaching myself with (Data Structures Using C and...
1
by: Foodbank | last post by:
Hi, I'm currently teaching myself C data structures in preparation for a job transition and I've just passed the point in which radix sorting was covered in my book. I've recently finished a...
3
by: Tracey | last post by:
I'm learning C++ and was stuck when writing code to convert a negative decimal number string to a hexdecimal number. For example, suppose the function interface is defined as: int atoi( const...
1
by: crimson08 | last post by:
does anyone know how to use radix sorting in a linked list???
0
by: Nick Keighley | last post by:
On Oct 25, 1:50 pm, Eric Sosman <esos...@ieee-dot-org.invalidwrote: since the pointer indicates the "last" digit. It indicates how many digits there are. I'm guessing that N is just some large...
8
by: tejas2991 | last post by:
could someone please gimme the main code for "radix sort" using stack
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.