Radix Sort Help

Discussion in 'C Programming' started by Foodbank, Oct 29, 2005.

  1. Foodbank

    Foodbank Guest

    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


    Code:
    #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 ***** */
    	
    
    }
    
     
    Foodbank, Oct 29, 2005
    #1
    1. Advertising

  2. On Sat, 29 Oct 2005 16:43:54 -0400, Foodbank <> 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 = 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

    --
    Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
     
    Arctic Fidelity, Oct 30, 2005
    #2
    1. Advertising

  3. Foodbank

    Thad Smith Guest

    Arctic Fidelity wrote:

    > On Sat, 29 Oct 2005 16:43:54 -0400, Foodbank <> 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 = 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.

    --
    Thad
     
    Thad Smith, Oct 30, 2005
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. senthil
    Replies:
    3
    Views:
    1,935
    prabinthomaskottayil
    Nov 25, 2011
  2. Kevin Doyle

    _ultoa radix??

    Kevin Doyle, Sep 8, 2003, in forum: C++
    Replies:
    18
    Views:
    991
    Kevin Goodsell
    Sep 9, 2003
  3. Tarique

    Radix Sort

    Tarique, Feb 1, 2008, in forum: C Programming
    Replies:
    3
    Views:
    731
    Tarique
    Feb 1, 2008
  4. none
    Replies:
    5
    Views:
    225
    John W. Krahn
    Nov 4, 2004
  5. Edward Wijaya

    Radix Sort in CPAN

    Edward Wijaya, Jan 20, 2005, in forum: Perl Misc
    Replies:
    9
    Views:
    141
    Tad McClellan
    Jan 21, 2005
Loading...

Share This Page