Сортировка Radix с использованием подсчета сортировки

Question

Этот алгоритм сортировки счисления использует сортировку подсчета в качестве требуемой в ней стабильной сортировки. Это правильно, если вводится 3 числа с небольшим количеством цифр, но алгоритм сортировки перестает работать для более высоких входных значений. Заранее спасибо

#include<stdio.h> 
    int digits(int k) 
    { 
     int i=0; 
     while(k!=0) 
     { 
      k=k/10; 
      i++; 
     } 
     return i; 
    } 
    void radixsort(int a[],int size,int k) 
    { 
     int c[10],b[50],i,j,l,m=10,n=1; 
     for(l=1;l<=k;l++) 
     { 
      if(l==1) 
      { 
       m=10; 
       n=1; 
      } 
      else 
      { 
       m=m*10; 
       n=n*10; 
      } 
      for(i=0;i<=9;i++) 
      { 
       c[i]=0; 
      } 
      for(j=1;j<=size;j++) 
      { 
       c[(a[j]%m)/n]=c[(a[j]%m)/n]+1; 
      } 
      for(i=0;i<=9;i++) 
      { 
       c[i]=c[i-1]+c[i]; 
      } 
      for(j=size;j>=1;j--) 
      { 
       b[c[(a[j]%m)/n]]=a[j]; 
       c[(a[j]%m)/n]--; 
      } 
      for(i=1;i<=size;i++) 
      { 
       a[i]=b[i]; 
      } 
     } 
    } 
    main() 
    { 
     int a[50],i,size,k=0; 
     printf("enter the size of the array\n"); 
     scanf("%d",&size); 
     printf("enter the numbers of the elements\n"); 
     for(i=1;i<=size;i++) 
     { 
      scanf("%d",&a[i]); 
      if(k<a[i]) 
      k=a[i]; 
     } 
     radixsort(a,size,k); 
     for(i=1;i<=size;i++) 
     { 
      printf("%d\n",a[i]); 
     } 
    } 

Answer 1

Перемещение части цикла перемещается от конца массива к началу, это не будет стабильным. Функция цифр никогда не вызывается. for (j = 1; ...) должен быть для (j = 0; j < size; ... Следующий цикл использует c [i-1], когда i равен нулю. Вместо этого вы можете использовать int c [11] из c [10] и использовать c [1+ (a [...] ...] ++, затем игнорировать c [10] при преобразовании отсчетов в индексы (c [0] = 0, c [1] = # 0's, c [2] = # 0's + # 1's, ...), затем перейдите от начала до конца (j = 0; j < size; ...). - rcgldr