C qsort работает неправильно

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

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

int compare(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

int main()
{
    int x[] = { -919238029,
            -889150029,
            -826670576,
            -579609061,
            -569653113,
            -305140505,
            -216823425,
            -193439331,
            -167683147,
            -49487019,
            -45223520,
            271789961,
            275570429,
            444855014,
            559132135,
            612312607,
            664554739,
            677860351,
            1005278191,
            1031629361,
            1089012280,
            1115952521,
            1521112993,
            1530518916,
            1907515865,
            1931470931,
            -1631034645,
            -1593702794,
            -1465300620,
            -1263094822
         };
    int i;

    qsort(x, 30, sizeof(int), compare);
    for(i = 0; i < 30; i ++)
        printf("%d\n", x[i]);

    return 0;
}

выводит следующий результат:

1521112993
1530518916
1907515865
1931470931
-1631034645
-1593702794
-1465300620
-1263094822
-919238029
-889150029
-826670576
-579609061
-569653113
-305140505
-216823425
-193439331
-167683147
-49487019
-45223520
271789961
275570429
444855014
559132135
612312607
664554739
677860351
1005278191
1031629361
1089012280
1115952521

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

Ответ 1

Да, ваше "сравнение" переполняется.: (

Причина:

Когда вы вычитаете отрицательное число из положительного числа, ваш результат не обязательно положителен; если он не может быть представлен в типе данных, он "обернется" с другой стороны.

Пример:

Если ваше целое число может содержать только от -8 до 7 (4 бит), то что происходит, когда вы сравниваете 4-4?

Ну, вы получаете 8, что 1000 в двоичном формате, которое равно -8. Таким образом, 4 меньше -4.

Мораль:

Не делать вычитание вместо сравнения, даже если они скажут вам "посмотрите, как это классно" в школе!

Ответ 2

В общем случае вы не можете использовать вычитание для сравнения целых чисел. Или, точнее, вы можете, но только в ситуациях, когда вы уверены, что вычитание не будет переполняться. В вашем случае вычитание излишков приводит к совершенно бессмысленным результатам (даже не говоря уже о том, что при переполнении целочисленного вычитания поведение не определено).

Общая идиома для генерации трехсоставных сравнений C-стиля между значениями a и b является выражением (a > b) - (a < b). Он работает для данных практически любых сопоставимых типов. В вашем случае функция сравнения может выглядеть следующим образом

int compare(const void* a, const void* b)
{
  int va = *(const int*) a;
  int vb = *(const int*) b;
  return (va > vb) - (va < vb);
}

Ответ 3

Я приводил пример кода, используя приведенную выше информацию. В моем компиляторе и системе я получаю те же результаты, что и Рам, который задал вопрос. Это указывает на то, что мои целые числа являются целыми числами Ram. Я изменил свой код по линиям, предложенным Мехрдадом, для использования операторов сравнения вместо вычитания. Затем я правильно отсортировал числа.

Вот код:

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

    int compare(const void* a, const void* b)
    {
        int
            n1 = * (int *) a,
            n2 = * (int *) b;

        /*
        Usine the ternary to express along the lines of
            if
            elseif
            elseif
            .
            .
            .
            else
        */

        return 
            n1 > n2             // if
            ? 1                 // then
            : n1 == n2          // else if
            ? 0                 // then
            : -1                // else
            ;                   // end if
    }

    int main(int argc, char * argv[])
    {
        int x[] = 
        { 
            -919238029, -889150029, -826670576, -579609061, -569653113, -305140505, -216823425, -193439331,
            -167683147, -49487019,  -45223520,  271789961,  275570429,  444855014,  559132135,  612312607,
            664554739,  677860351,  1005278191, 1031629361, 1089012280, 1115952521, 1521112993, 1530518916,
            1907515865, 1931470931, -1631034645,-1593702794,-1465300620,-1263094822
        };

        int 
            i = 0,                          // index
            imax = sizeof(x)/sizeof(int);   // max value for index

        FILE * outf = 0;

        if ( !(outf = fopen("output.txt", "wt")) )
        {
            puts("outf == 0 which is an error trying to open \"output.txt\" for writing.\n");
            getch();
            return;
        }

        qsort(x, imax, sizeof(int), compare);


        for(i = 0; i < imax; i ++)
            fprintf(outf, "%d\n", x[i]);

        fclose(outf);

        return 0;
    }

И я получаю этот вывод:

-1631034645
-1593702794
-1465300620
-1263094822
-919238029
-889150029
-826670576
-579609061
-569653113
-305140505
-216823425
-193439331
-167683147
-49487019
-45223520
271789961
275570429
444855014
559132135
612312607
664554739
677860351
1005278191
1031629361
1089012280
1115952521
1521112993
1530518916
1907515865
1931470931

Ответ 4

Чтобы добавить к Mehrad правильный ответ, здесь автоматический способ найти ошибку в вашем коде с помощью SortChecker:

$ LD_PRELOAD=$HOME/sortcheck-master/bin/libsortcheck.so ./a.out
a.out[38699]: qsort: comparison function is not transitive (comparison function 0x40057d (/home/iuriig/a.out+0x40057d), called from 0x400693 (/home/iuriig/a.out+0x400693), cmdline is "./a.out")
-919238029
-889150029
...

Это предупреждение говорит, что compare отчеты x < y, y < z а не x < z для некоторых входов. Чтобы отладить эту проблему, выполните

export SORTCHECK_OPTIONS=raise=1

и исследовать сгенерированный codedump.