Функция сравнения qsort не упорядочивает весь массив (исключает 1 элемент)

Question

Соответствующий код (индекс - это размер массива):

typedef struct elemento {
    unsigned long linha;
    unsigned long coluna;
    double valor;
} elemento; 

elemento Representados[MAXN];
qsort(Representados, index, sizeof(Representados[0]), lcomparator);

int lcomparator(const void *el1, const void *el2) {
    int l1 = ((elemento *)el1)->linha;
    int l2 = ((elemento *)el2)->linha;
    int c1 = ((elemento *)el1)->coluna;
    int c2 = ((elemento *)el2)->coluna;

    if (l1 < l2) {
        return -1;
    }
    else if (l1 == l2) {
        if (c1 < c2) {
            return -1;
        }
        else if (c1 == c2) {
            return 0;
        }
        else if (c2 > c1) {
            return 1;
        }
    }
    else {
        return 1;
    }

}

gcc также выводит предупреждение «конец достижения контроля» для lcomparator, но я не понимаю, как моя функция могла бы ничего не возвращать.

Answer 1

Чтобы добавить к уже правильному ответу @Stargateur, вот автоматический способ найти ошибку в вашем коде, используя SortChecker :

LD_PRELOAD=$HOME/SortCheck/bin/libsortcheck.so ./a.out
a.out[3024]: qsort: comparison function is not symmetric (comparison function 0x400526 (/home/yugr/src/so/a.out+0x400526), called from 0x4005c6 (/home/yugr/src/so/a.out+0x4005c6), cmdline is "./a.out")

Это предупреждение говорит о том, что lcomparator возвращаетпротиворечивые результаты при смене порядка аргументов.Для дальнейшей отладки этой проблемы запустите с

export SORTCHECK_OPTIONS=raise=1

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

Answer 2

else if (c2 > c1) {
    return 1;
}

неверно и должно быть

else if (c1 > c2) {
    return 1;
}

или лучше

else {
    return 1;
}

и, конечно, заменить int на unsigned long

Answer 3

Предыдущие комментарии и ответы уже показали разницу в типах между unsigned long и int и ошибку сравнения. Ваш код может на практике всегда возвращать значение, но компилятору не нравится зависание else.

Я предлагаю следующее:

int lcomparator(const void *el1, const void *el2) {
    unsigned long l1 = ((elemento *)el1)->linha;
    unsigned long l2 = ((elemento *)el2)->linha;
    unsigned long c1 = ((elemento *)el1)->coluna;
    unsigned long c2 = ((elemento *)el2)->coluna;

    if(l1 < l2) {
        return -1;
    } 
    if(l1 > l2) { 
        return 1;
    } 
    if(c1 < c2) { 
        return -1;
    } 
    if(c1 > c2) {
        return 1;
    }
    return 0;
}

Answer 4

Мое предложение:

1. Измените типы локальных переменных функции на unsigned long.Вы теряете точность, когда они имеют тип int.Это может быть источником проблемы, с которой вы сталкиваетесь, но трудно сказать без фактических значений.

2. Логика ядра может быть упрощена с помощью вспомогательной функции.

Вот обновленная версия вашей функции.

int compare_helper(unsigned long l1, unsigned long l2)
{
   if ( l1 < l2 )
   {
      return -1;
   }
   if ( l2 < l1 )
   {
      return 1;
   }
   return 0;

   // The line below does the same thing but relies on the logical expressions 
   // to be 1 or 0.
   // return (l2<l1) - (l1<l2);
}

int lcomparator(const void *el1, const void *el2) {
    unsigned long l1 = ((elemento *)el1)->linha;
    unsigned long l2 = ((elemento *)el2)->linha;
    unsigned long c1 = ((elemento *)el1)->coluna;
    unsigned long c2 = ((elemento *)el2)->coluna;

    if ( l1 != l2 )
    {
       return compare_helper(l1, l2);
    }

    return compare_helper(c1, c2);
}