Radix Sort

Discussion in 'C Programming' started by Tarique, Feb 1, 2008.

  1. Tarique

    Tarique Guest

    Hello.
    I have tried to implement Radix Sort. Can anyone please help
    me fix the bug.For the time being i assume all my data(to be sorted)
    are of 2 digits.


    I ran the code under a debugger.And i see that all the data are properly
    hashed to their positions.The error seems to be the retrieval and
    rearrangement of data into the array.


    Here is the code :

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define NKEYS (sizeof x/sizeof x[0])

    struct node{
    int data;
    struct node *next;
    };

    struct node* get_node(int n)
    {
    struct node *z;
    z = malloc(sizeof *z);
    if(z != NULL)
    {
    z->data = n;
    z->next = NULL;
    return z;
    }

    return NULL;
    }

    void radixsort(int *x,int n)
    {
    int i = 0 , j ,k ;
    struct node *z;
    struct node *p;
    struct node *hashtable[10];
    struct node *hashend[10];

    for(i = 0; i < 10; i++)
    {
    hashtable = (z = get_node(i));
    hashend = (z = get_node(i));
    }

    for( k = 1; k < 3 ; k++)
    {
    for(i = 0; i < n; i++)
    {
    j = (x/(int)pow(10,k-1)) % 10;
    z = get_node(x); /*Did not check return value*/

    if( hashtable[j]->next == NULL ) {
    hashtable[j]->next = z;
    hashend[j]->next = z;
    }
    else {
    hashend[j]->next->next = z;
    hashend[j]->next = z;
    }
    }

    /*This seems to be the bugged part */
    for(j = 0; i < n ; j++)
    {
    p = hashtable[j];
    while( p->next != NULL )
    {
    x[i++] = p->data;
    p = p->next;
    }
    }
    }
    return ;
    }

    int main(void)
    {
    int i;
    int x[] = {34,87,84,23,99};

    radixsort(x,NKEYS);

    for(i = 0;i < NKEYS; i++)
    printf("%d ",x);

    return 0;
    }

    Thank You
    Tarique, Feb 1, 2008
    #1
    1. Advertising

  2. Tarique

    Tarique Guest

    Tarique wrote:
    ....snip...

    Fixed it.Kindly ignore the message
    Tarique, Feb 1, 2008
    #2
    1. Advertising

  3. Just to be kind with the other users you could post the solution
    ;-)

    On 1 fev, 15:45, Tarique <> wrote:
    > Tarique wrote:
    >
    > ...snip...
    >
    > Fixed it.Kindly ignore the message
    Leonardo Korndorfer, Feb 1, 2008
    #3
  4. Tarique

    Tarique Guest

    Leonardo Korndorfer wrote:
    > Just to be kind with the other users you could post the solution
    > ;-)


    There you go brother :p

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define NKEYS (sizeof x/sizeof x[0])

    struct node{
    int data;
    struct node *next;
    };

    struct node* get_node(int n)
    {
    struct node *z;
    z = malloc(sizeof *z);
    if(z != NULL)
    {
    z->data = n;
    z->next = NULL;
    return z;
    }
    return NULL;
    }

    void radixsort(unsigned int *x,int n)
    {
    int i = 0 , j = 0;
    int digit = 0;
    struct node *z;
    struct node *p;
    struct node **old ;
    struct node *hashtable[10];
    struct node *hashend[10];

    for( digit = 1; digit < 8; digit++) /*can handle integers upto 7
    digits(arbitrary right now)*/
    {

    /*Initialise the hash tables*/
    for(i = 0; i < 10; i++)
    {
    hashtable = (z = get_node(i));
    hashend = (z = get_node(i));
    }

    /*Parse through the array*/
    for(i = 0; i < n; i++)
    {
    j = (x/(int)pow(10,digit-1)) % 10; /*Get Individual digts*/
    z = get_node(x); /*Create a node with parsed value*/


    /*No hashing as yet*/
    if( hashtable[j]->next == NULL ) {
    hashtable[j]->next = z;
    hashend[j]->next = z;
    }
    /*Hashed value present*/
    else {
    hashend[j]->next->next = z;
    hashend[j]->next = z;
    }
    }

    j=0; /*j was used earlier so fix it up again*/
    for(i = 0; i < 10 ; i++)
    {
    /*For each index in hashtable,parse thorugh the nodes */
    for(p = hashtable->next; p != NULL ; p = p->next)
    {
    if(p == NULL)
    break;
    x[j++] = p->data; /*Use the passed array to store new values*/
    } /*after each pass*/
    }


    /*Free up the nodes before the next pass*/
    for(i = 0; i < 10 ; i++)
    {
    old = &hashtable->next;
    if(old != NULL && *old != NULL) {
    free(*old);
    *old = NULL;
    }
    }

    }
    return ;
    }


    /*The routine sorts only positive numbers*/
    int main(void)
    {
    int i;
    unsigned int x[] = {8966,12,45,89,552};

    radixsort(x,NKEYS);

    for(i = 0;i < NKEYS; i++)
    printf("%d ",x);

    return 0;
    }
    Tarique, Feb 1, 2008
    #4
    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,859
    prabinthomaskottayil
    Nov 25, 2011
  2. Kevin Doyle

    _ultoa radix??

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

    Radix Sort Help

    Foodbank, Oct 29, 2005, in forum: C Programming
    Replies:
    2
    Views:
    462
    Thad Smith
    Oct 30, 2005
  4. none
    Replies:
    5
    Views:
    192
    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:
    119
    Tad McClellan
    Jan 21, 2005
Loading...

Share This Page