2016-02-19 13 views
0

Я пытаюсь написать алгоритм сортировки Radix в C. Когда я запускаю свой код с базой 10, он отлично работает для всех входов, однако с базой 16 он правильно сортирует только первые 10 элементов. Кроме того, для любой другой базы он не работает. Я хотел бы сделать реализацию, которая обобщает для любой базы.Реализация Radix sort

Код пользователя a до сих пор, не могли бы вы найти какие-либо проблемы?

#include <stdio.h> 
#include <stdlib.h> 
int size=32; 
int getMax(int arr[], int n) { 
    int mx = arr[0]; 
    int i; 
    for (i = 1; i < n; i++) 
     if (arr[i] > mx) 
      mx = arr[i]; 
    return mx; 
} 

void countSort(int arr[], int n, int exp, int base) { 
    int output[n]; 
    int i; 
    int count[base]; 
    memset(count,0,sizeof count); 
    for (i=0;i<n;i++) 
     count[(arr[i]/exp)%base]++; 
    for (i=1;i<base;i++) 
     count[i]=count[i]+count[i-1]; 
    for (i=n-1;i>=0;i--) { 
     output[count[ (arr[i]/exp)%base ]-1]=arr[i]; 
     count[ (arr[i]/exp)%base ]--; 
    } 
    for (i=0;i<n;i++) 
     arr[i]=output[i]; 
} 

void radixsort(int arr[],int n,int base) { 
    int exp; 
    int m=getMax(arr,n); 
    for (exp=1;m/exp>0;exp=exp*10) 
    countSort(arr,n,exp,base); 
} 

int main(int argc,char *argv[]) {  
    int num,i=0,j,n,m; 
    int *arr,*newarr=NULL; 
    FILE *fp1; 
    FILE *fp2; 
    int base=atoi(argv[1]); 
    fp1=fopen(argv[2],"r"); 
    if (fp1 == NULL) { 
    printf("Warning:File does not exists;please enter valid file name"); 
    exit(0); 
    } 
    fp2=fopen(argv[3],"w"); 
    if (fp2 == NULL) { 
     printf("Warning:File does not exists"); 
     exit(0); 
    } 
    arr= malloc(sizeof(int)*size); 
    fprintf(fp2,"before sorting:"); 
    while(fscanf(fp1,"%d",&num)==1) { 
    if(i<size) { 
     arr[i]=num; 
     i++; 
     fprintf(fp2,"%d ",num); 
     n=i; 
    } else { 
     newarr = malloc(sizeof(int)*2*size); 
     for(m=0;m<size;m++) { 
      newarr[m]=arr[m]; 
     } 
     free(arr); 
     size=size*2; 
     arr=&newarr[0]; 
    } 
    } 
    radixsort(arr,n,base); 
    fprintf(fp2,"\nAfter Sorting:"); 
    for (j=0;j<n;j++) 
    fprintf(fp2,"%d ",arr[j]); 

    fclose(fp1); 
    fclose(fp2); 
    return 0; 
} 
+0

почему вы не просто преобразовать число по основанию 10? – Jacobr365

ответ

0

Похоже, for (exp=1;m/exp>0;exp=exp*10). Я думаю, вам нужно использовать base вместо 10.

EDIT: Я пытался скомпилировать и запустить этот код и не смог заставить его работать, даже для основания 10.

+0

Извините .. я не знаю, почему он не работает на вашей стороне, но он отлично работает, когда я выполнил его с базой 10 .. – Trisha

+0

Работает ли она на других базах с изменением, которое я предложил? –