Bubble sort занимает больше времени, чем segfaults

Question

Учитывая целое число n, напишите программу на C для подсчета количества цифр, которые находятся в той же позиции после формирования целого числа m с цифрами в n, но в порядке возрастания цифр. Например, если значение n равно 351462987, то значение m будет равно 123456789, а цифры 4 и 8 будут в том же положении.

Это мой код:

#include<stdio.h>

void bubble(int a[],int length)
{
    for (int i=0;i<length;i++)
    {
        for (int j=0;j<length;j++)
        {
            if (a[j]>a[j+1])
            {
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
}
int check(int a[],int b[],int length)
{
    int count=0;
    for (int i=0;i<length;i++)
    {
        if (a[i]==b[i])
        {
            count=i;
            break;
        }
    }
    return count;
}
int length(int n)
{
    int l;
    while (n!=0)
    {
        n=n/10;
        l++;
    }
    return l;
}
void main()
{
    int n,arrn[100],temp[100];
    scanf("%d",&n);
    int l=length(n);
    for (int i=0;i<l;i++)
    {
        arrn[l-i-1]=n%10;
        temp[l-i-1]=arrn[l-i-1];
        n=n/10;
    }
    bubble(temp,l);
    int c=check(arrn,temp,l);
    printf("%d",c);
}

Я могу скомпилировать код, но когда я его выполняю, требуется только много времени, чтобы показать ошибку сегментации.

Answer 1

Простой ответ, используйте отладчик .

Вот некоторые проблемы с вашим кодом:

• В функции length l не инициализируется и поэтому может иметь произвольное начальное значение. В вашем случае вы, вероятно, хотите начать с 0.

  int l = 0;
  

• Ваша check функция, вероятно, не делает то, что вы хотите. Как написано, count - не счет, а индекс позиции, в которой совпадают числа. Поскольку в блоке есть оператор break, цикл завершится после первого совпадения, поэтому возвращаемым значением будет позиция первого совпадения или 0, если совпадение не найдено.

• Ваша функция bubble переходит на один элемент слишком далеко, когда i равен length - 1, когда вы получаете доступ к элементу a[j + 1] во внутреннем цикле, который находится за пределами. В этом случае проще начать с 1 вместо 0 и сравнить элемент с индексом i - 1 с элементом с индексом i.

Некоторые дополнительные заметки:

• Рекомендуется добавлять пробелы вокруг операторов и после запятой, разделяя несколько объявлений, чтобы улучшить читаемость. Вот несколько примеров строк с улучшенной читаемостью.

  int n, arrn[100], temp[100];
  int count = 0;
  for (int i = 0; i < length; i++)…
  if (a[i] == b[i])…
  arrn[l - i - 1] =n % 10;
  temp[l - i - 1] = arrn[l - i - 1];
  int check(int a[], int b[], int length)
  

• Вместо написания нескольких функций одновременно, вы должны написать одну функцию и убедиться, что она работает правильно. Кстати, цикл, который разбивает число на цифры, также может быть функцией.

  • Попробуйте функцию с небольшим числом (например, 12 или 21)
  • Используйте лучшее имя для вашей переменной. arrn и temp не очень понятны. original и sorted могут быть лучше.

Answer 2

Лично я бы не стал сортировать или читать его в целое число - чтобы можно было обрабатывать начальные нули в строке цифр. Например:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXNUMLEN 200
int main(void)
{
   int i, j, l, x=0;
   char numin[MAXNUMLEN], numout[MAXNUMLEN];
   int digits[10]={0};

   printf("enter a string of digits: " );
   fgets(numin, sizeof(numin), stdin); 
   printf("\nsaw   : %s", numin );

   // walk string once, counting num of each digit present
   l=strlen(numin);
   for(i=0; i<l; i++) {
      if( isdigit(numin[i]) ) {
         int d = numin[i] - '0'; // char digit to int digit
         digits[d]++;
      }
   }

   // for each digit present, write the number of instances of the digit to numout
   for( i=0; i<10; i++ ) {
      for(j=0; j<digits[i]; j++)
         numout[x++] = '0'+i; // int digit back to char digit
   }
   numout[x]='\0'; // terminate string
   printf("sorted: %s\n", numout );
}

Пример прогона:

watson:digsort john$ ./ds
enter a string of digits: 002342123492738234610

saw   : 002342123492738234610
sorted: 000112222233334446789
watson:digsort john$ 

Answer 3

Ваша функция длины имеет очень очевидную ошибку. С какого значения начинается l? Вы не инициализируете его, чтобы оно могло начинаться с любого значения и вызывало неопределенное поведение. Вы должны установить его на 0.

int length(int n)
{
    int l = 0;
    while (n!=0)
    {
        n=n/10;
        l++;
    }
    return l;
}