Блог

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

Например:

 "5 > 11" because 5 > 1 1 (5 > 2). 
 

Мне удалось отсортировать суммы, но возможно ли вернуться к исходным числам или сделать это другим способом?

 #include <stdio.h>
void sortujTab(int tab[], int size){
    int sum,i;
    for(int i=0;i<size;i  )
    {
        while(tab[i]>0){//sum as added digits of an integer
            int p=tab[i]%10;
            sum=sum p;
            tab[i]/=10;
        }

        tab[i]=sum;
        sum=0;
    }
    for(int i=0;i<size;i  )//print of unsorted sums
    {
        printf("%d,",tab[i]);
    }
    printf("n");
    for(int i=0;i<size;i  )//sorting sums
        for(int j=i 1;j<=size;j  )

        {
            if(tab[i]>tab[j]){
                int temp=tab[j];
                tab[j]=tab[i];
                tab[i]=temp;

            }
        }
    for(int i=0;i<20;i  )//print of sorted sums
    {
        printf("%d,",tab[i]);
    }
}
int main()
{
    int tab[20];
    int size=sizeof(tab)/sizeof(*tab);
    for(int i=0;i<=20;i  )
    {
        tab[i]=rand()%1000;// assamble the value
    }
    for(int i=0;i<20;i  )
    {
        printf("%d,",tab[i]);//print unsorted
    }
    printf("n");

    sortujTab(tab,size);

    return 0;
}
 

Существует два основных подхода :

1. Создайте функцию, которая возвращает сумму для целого числа, скажем sum(int a) , затем вызовите ее при сравнении, чтобы вместо tab[i] > tab [j] нее стало sum(tab[i]) > sum (tab[j])
2. Сохраните сумму в другом массиве, сравните с новым массивом и при замене поменяйте местами исходный и новый массив

Первое решение работает достаточно хорошо, если массив небольшой и не занимает дополнительной памяти, в то время как второму решению не нужно было повторно вычислять сумму. Также возможен подход к кэшированию map , но оно того стоит, только если в массиве достаточно одинаковых чисел.

Поскольку ваши числа неотрицательны и меньше 1000, вы можете закодировать сумму цифр в самих числах. Итак, эта формула будет верна: encoded_number = original_number 1000 * sum_of_the_digits . encoded_number/1000 декодирует сумму цифр и encoded_number00 декодирует исходное число. Следуйте измененному коду ниже. Числа, заключенные в круглые скобки в выходных данных, являются исходными числами. Я попытался минимально изменить ваш код.

 #include <stdio.h>
#include <stdlib.h>

void sortujTab(int tab[], int size)
{
    for (int i = 0; i < size; i  ) {
        int sum = 0, n = tab[i];
        while (n > 0) { //sum as added digits of an integer
            int p = n % 10;
            sum = sum   p;
            n /= 10;
        }    
        tab[i]  = sum * 1000;
    }
    for (int i = 0; i < size; i  ) { //print of unsorted sums
        printf("%d%c", tab[i] / 1000, i < size - 1 ? ',' : 'n');
    }

    for (int i = 0; i < size; i  ) { //sorting sums
        for (int j = i   1; j < size; j  ) {
            if (tab[i] / 1000 > tab[j] / 1000) {
                int temp = tab[j];
                tab[j] = tab[i];
                tab[i] = temp;
             }
        }
    }

    for (int i = 0; i < size; i  ) { //print of sorted sums
        printf("%d(%d)%c", tab[i] / 1000, tab[i] % 1000, i < size - 1 ? ',' : 'n');
    }
}

int main(void)
{
    int tab[20];
    int size = sizeof(tab) / sizeof(*tab);
    for (int i = 0; i < size; i  ) {
        tab[i] = rand() % 1000; // assamble the value
    }
    for (int i = 0; i < size; i  ) {
        printf("%d%c", tab[i], i < size - 1 ? ',' : 'n'); //print unsorted
    }

    sortujTab(tab, size);

    return 0;
}
 

Если диапазон чисел не допускает такой кодировки, то вы можете объявить структуру с двумя целочисленными элементами (один для исходного числа и один для суммы его цифр), выделить массив для size элементов этой структуры и инициализировать и отсортировать массив, используя суммы цифр в качестве ключей.

Вы можете сортировать массив индексов, а не массив с данными.

 #include <stdio.h>

//poor man's interpretation of sumofdigits() :-)
int sod(int n) {
    switch (n) {
        default: return 0;
        case 5: return 5;
        case 11: return 2;
        case 1000: return 1;
        case 9: return 9;
    }
}

void sortbyindex(int *data, int *ndx, int size) {
    //setup default indexes
    for (int k = 0; k < size; k  ) ndx[k] = k;
    //sort the indexes
    for (int lo = 0; lo < size; lo  ) {
        for (int hi = lo   1; hi < size; hi  ) {
            if (sod(data[ndx[lo]]) > sod(data[ndx[hi]])) {
                //swap indexes
                int tmp = ndx[lo];
                ndx[lo] = ndx[hi];
                ndx[hi] = tmp;
            }
        }
    }
}

int main(void) {
    int data[4] = {5, 11, 1000, 9};
    int ndx[sizeof data / sizeof *data];

    sortbyindex(data, ndx, 4);

    for (int k = 0; k < sizeof data / sizeof *data; k  ) {
        printf("%dn", data[ndx[k]]);
    }

    return 0;
}