Radix Sort

[Tarique]

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]

Tarique wrote:
....snip...

Fixed it.Kindly ignore the message

 

[Leonardo Korndorfer]

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

 

[Tarique]

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 = (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;
}