Velocity Reviews > Radix Sort

# Radix Sort

Tarique
Guest
Posts: n/a

 02-01-2008
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[i] = (z = get_node(i));
hashend[i] = (z = get_node(i));
}

for( k = 1; k < 3 ; k++)
{
for(i = 0; i < n; i++)
{
j = (x[i]/(int)pow(10,k-1)) % 10;
z = get_node(x[i]); /*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[i]);

return 0;
}

Thank You

Tarique
Guest
Posts: n/a

 02-01-2008
Tarique wrote:
....snip...

Fixed it.Kindly ignore the message

Leonardo Korndorfer
Guest
Posts: n/a

 02-01-2008
Just to be kind with the other users you could post the solution

On 1 fev, 15:45, Tarique <(E-Mail Removed)> wrote:
> Tarique wrote:
>
> ...snip...
>
> Fixed it.Kindly ignore the message

Tarique
Guest
Posts: n/a

 02-01-2008
Leonardo Korndorfer wrote:
> Just to be kind with the other users you could post the solution
>

There you go brother

#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[i] = (z = get_node(i));
hashend[i] = (z = get_node(i));
}

/*Parse through the array*/
for(i = 0; i < n; i++)
{
j = (x[i]/(int)pow(10,digit-1)) % 10; /*Get Individual digts*/
z = get_node(x[i]); /*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[i]->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[i]->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[i]);

return 0;
}

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post senthil VHDL 3 11-25-2011 11:58 AM Foodbank C Programming 2 10-30-2005 03:51 AM Edward Wijaya Perl Misc 9 01-21-2005 11:09 PM none Perl Misc 5 11-04-2004 07:37 AM Navin ASP General 1 09-09-2003 07:16 AM

Advertisments