radixsort.c

/**************************************************************************************/
/* Radix Sort of integers numbers  using polymorphic linked lists.   */
/**************************************************************************************/

#include <stdio.h>
#include "list.h"
#include <stdlib.h>
#include "numberinterface.h"
#include <math.h>

void static refill( int A[] , list Bins[] ) ;
int  static getdigit( int number, int position ) ;

int main( int argc, char *argv[] ) {

  int *A   ;
  list Bins[10]   ;
  int i, j, k, n, digit ;

  n = atoi( argv[1] ) ;
  A = (int *)malloc( sizeof( int) * n ) ;

  for ( i = 0 ; i <  n  ; i++ ) { A[i] = rand() % 10000; } 

  printf("\n        ");
  for ( i = 0 ; i <  20 ; i++ ) printf(" %d ", A[i] );    

  printf("\n");
  for ( i = 0 ; i <  10 ; i++ ) init_list( &Bins[i] ) ;

  for ( i = 1 ; i <= 4 ; i++ ) {
    printf("Pass %d: ", i ) ;
    for ( j = 0 ; j < n ; j++ ) {

      digit = getdigit( A[j] , i-1 ) ;
      appendanumber( &Bins[digit], A[j] ) ; 

    }

    refill( A, Bins ) ;
    for ( k = 0 ; k < 20 ; k++ ) printf(" %d ", A[k] );   printf("\n");
  }

  return 0 ;
}

static int getdigit( int num, int position ) {

  int digit = num / (int)pow(10,position-1) % 10 ;

  return  digit ;  




}

static void refill( int A[], list Bins[] ) {

  int i            ;
  int j = 0        ;
  int n            ;

  for( i = 0 ; i < 10 ; i++ ){

    while( !empty_list( Bins[i] ) ) { 
      
      getnextnumber(&Bins[i] , &n) ; 
      A[j] = n ; 
      j++ ; 



    }
  }
}

numberinterface.h

#ifndef _numberinterface
#define _numberinterface

#include "list.h"

extern status appendanumber( list *p_L , int n ) ; 
extern status getnextnumber( list *p_L , int *p_n ) ; 

#endif

numberinterface.c

#include <stdlib.h>
#include "numberinterface.h"
#include "globals.h" 
#include "list.h"
#include <stdio.h>

status appendanumber( list *p_L , int n ){ 

	int *t_ptr = (int *)malloc(sizeof(int) ) ;
	
	if( t_ptr == NULL ) return ERROR ; 

	*t_ptr = n ; 


	if( append(p_L,(generic_ptr)t_ptr) == ERROR ) {free(t_ptr ) ; return ERROR ; } 

	


	return OK ; 

}


status getnextnumber( list *p_L , int *p_n ){

	
int *p_temp ; 

if(delete(p_L, (generic_ptr *)&p_temp ) == ERROR ) return ERROR ; 

	*p_n = *p_temp ; 

	free(p_temp) ; 

	return OK ; 

}

list.h

#ifndef _list
#define _list

#include "globals.h"

typedef struct node node, *list;

struct node { generic_ptr datapointer; list next; };

extern status allocate_node( list *p_L, generic_ptr data ) ;

extern void   free_node( list *p_L ) ;

extern status init_list( list *p_L ) ;

extern bool   empty_list( list L ) ;

extern status insert( list *p_L, generic_ptr data ) ;

extern status append( list *p_L, generic_ptr data ) ;

extern status delete( list *p_L, generic_ptr *p_data ) ;

extern status delete_node( list *p_L, list node ) ;

extern status traverse( list L, status (*p_func_f) () );

extern status find_key( list L, generic_ptr key, int(*p_cmp_f) (), list *p_keynode );

extern list list_iterator( list L, list lastreturn );

extern void destroy(list *p_L, void (*p_func_f)() );

extern bool set_equal( list L1 , list L2 , int (*p_cmp_f)() ) ; 

#endif

list.c

/*****************************************************************************/
/* list.c                                                                    */
/*                                                                           */
/*****************************************************************************/

#include <stdlib.h>
#include "globals.h"
#include "list.h"

status allocate_node( list *p_L , generic_ptr data)  {


  list L = (list) malloc(sizeof(node));

  if (L == NULL) return ERROR;

  *p_L = L;
  
  DATA(L) = data;
  NEXT(L) = NULL;
  return OK;

}


void free_node(list *p_L) {

  free(*p_L);
  *p_L = NULL;

}

status init_list( list *p_L) {

  *p_L = NULL;
  return OK;

}

bool empty_list(list L) {

  return (L == NULL ) ? TRUE : FALSE;

}

status insert( list *p_L,generic_ptr data ) {

  list L;
  
  if(allocate_node(&L, data) == ERROR) return ERROR;

  NEXT(L) = *p_L;
  *p_L = L; 
  return OK;

}

status append(list *p_L, generic_ptr data) {

  list L, tmplist;
  if(allocate_node(&L, data) == ERROR) return ERROR;

  if(empty_list(*p_L) == TRUE) *p_L = L;

  else {
    for(tmplist = *p_L; NEXT(tmplist) != NULL; tmplist=NEXT(tmplist) );
    NEXT(tmplist) = L;

  }

  return OK;

}

status delete(list *p_L, generic_ptr *p_data) {

  if(empty_list(*p_L)) return ERROR;

  *p_data = DATA(*p_L);

return delete_node(p_L, * p_L);

}

status delete_node( list *p_L, list node) {

  if(empty_list(*p_L) == TRUE) return ERROR;

  if(*p_L == node) *p_L = NEXT(*p_L);

  else {
    list L;
    for(L = *p_L; L != NULL && NEXT(L) != node; L = NEXT(L));

    if (L == NULL) return ERROR;
    else NEXT(L) = NEXT(node);

  }

  free_node(&node);
  return OK;

}




status traverse( list L, status(*p_func_f) () ) {

  if(empty_list(L)) return OK;

  if( (*p_func_f)(DATA(L)) == ERROR ) return ERROR;

  else
    return traverse(NEXT(L), p_func_f);

}


status find_key( list L, generic_ptr key, int(*p_cmp_f)(), list *p_keynode ) {

  list curr = NULL;
  
  while( ( curr = list_iterator(L, curr)) != NULL) {

    if ( (*p_cmp_f) (key, DATA(curr) ) == 0 ) {

      *p_keynode = curr;
      return OK;
    }
  }
  return ERROR;
}


list list_iterator(list L, list lastreturn ) {

  return (lastreturn == NULL) ? L : NEXT(lastreturn);

}


void destroy( list *p_L, void (*p_func_f)() ) {

  if (empty_list(*p_L) == FALSE) {

    destroy( &NEXT(*p_L), p_func_f );
    
    if (p_func_f != NULL) 
	
   (*p_func_f)(DATA(*p_L));
    
    free_node(p_L);

  }
} 


bool equal(list L1 , list L2 , int (*p_cmp_f)() ){

while(L1 != NULL && L2 != NULL ){
if( (*p_cmp_f)(L1->datapointer,L2->datapointer ) == -1)
return FALSE;

else
equal(L1->next,L2->next,p_cmp_f) ; 
}


return TRUE;
}



bool set_equal( list L1 , list L2 , int (*p_cmp_f)() ){

	 
while(L1 != NULL && L2 != NULL ){
if( (*p_cmp_f)(L1->datapointer,L2->datapointer ) == -1)
return FALSE;

else
equal(L1->next,L2->next,p_cmp_f) ; 
}

return TRUE;
}

globals.h

#ifndef _globals
#define _globals

#define NEXT(L) ( (L) -> next )

#define DATA(T) ( (T) -> datapointer )
#define LEFT(T) ( (T) -> left )
#define RIGHT(T) ( (T) -> right )

typedef enum { OK, ERROR } status ;
typedef enum { FALSE=0 , TRUE=1 } bool ;
typedef void *generic_ptr ;

#endif

I compiled it like this : gcc -o radix radixsort.c list.c numberinterface.c -lm

and after I ran it it printed this out:

./radix 5

9383 886 2777 6915 7793 135145 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Floating point exception

so i decided to compile it with the -g option and run it on gdb
and this is what i got:

(gdb) run
Starting program: ........................../radixsort/radix

Program received signal SIGSEGV, Segmentation fault.
0x0054becc in ____strtol_l_internal () from /lib/tls/libc.so.6
(gdb)

Edited 5 Years Ago by rockerjhr: n/a

Your call to atoi may be failing.

From my help file

The atoi() function converts the initial portion of the string pointed
to by nptr to int. The behavior is the same as

strtol(nptr, (char **) NULL, 10);

except that atoi() does not detect errors.

Try using strtol() instead.

Edited 5 Years Ago by gerard4143: n/a

The problem is not related to atoi().

static int getdigit( int num, int position ) {

  int digit = num / (int)pow(10,position-1) % 10 ;

  return  digit ;

division by 0 problem. pow() is returning 0 probably because the second parameter to pow() is a negative number (the value of position is 0)

Edited 5 Years Ago by Ancient Dragon: n/a

This article has been dead for over six months. Start a new discussion instead.