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

Этот алгоритм сортировки по основанию использует сортировку подсчетом в качестве требуемой стабильной сортировки. Это правильно сортируется при вводе 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]);
        }
    }

person Koosh Doctor    schedule 16.06.2015    source источник
comment
Пожалуйста, прокомментируйте свою реализацию и дайте осмысленные имена переменным. Неразумно ожидать, что кто-то добровольно просмотрит такие строки, как b[c[(a[j]%m)/n]]=a[j];. Вам также, вероятно, нужно где-то вызвать функцию digits. Возможно, что-то вроде radixsort(a,size,digits(k)) было бы правильным.   -  person n. 1.8e9-where's-my-share m.    schedule 16.06.2015
comment
извините @n.m. Имейте это в виду в следующий раз. Большое спасибо. Приносим извинения за неудобства   -  person Koosh Doctor    schedule 16.06.2015
comment
Движущаяся часть цикла движется от конца массива к началу, это не будет стабильным. Функция цифр никогда не вызывается. for(j=1; ... ) должно быть for(j = 0; j ‹ size; ... Следующий цикл использует c[i-1], когда i равно нулю. Вместо этого вы можете использовать int c[11] из c[10] и используйте c[1+(a[ ...] ...] ++, затем игнорируйте c[10] при преобразовании счетчиков в индексы (c[0] = 0, c[1] = #0, c[2] = #0 + #1, ...), затем переход от начала к концу (j=0; j ‹ размер; ...) .   -  person rcgldr    schedule 16.06.2015
comment
Я использовал функцию цифр, и чтобы сделать ее стабильной, я начал с самого высокого индекса. теперь работает нормально   -  person Koosh Doctor    schedule 16.06.2015


Ответы (1)


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

person Community    schedule 09.11.2015