Странное поведение C qsort

Я пытаюсь сделать следующее:

  1. Выделить память для массива размерности 7
  2. Напишите первые 4 позиции
  3. Отсортируйте эти 4 позиции.
  4. Напишите оставшиеся 3 позиции
  5. Отсортируйте весь массив.

У меня есть массив (1,6,2,3), который после сортировки становится (1,2,3,6)

Затем я записываю оставшиеся позиции, а именно (1,2,3,6,1,5,1)

После сортировки я должен получить (1,1,1,2,3,5,6), но вместо этого я получаю (6,2,3,1,1,5,1).

Вот код:

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

int comp(const void* a, const void* b);

typedef struct{

    int peso;
 }aresta_;

int main(int argc, const char * argv[]) {

    aresta_* array /*struct array, has field peso of type int*/;
    int dim=7;
    int dim_aux=4;
    int i;

    array = (aresta_*) malloc(dim * sizeof(aresta_));

    array[0].peso=1;
    array[1].peso=6;
    array[2].peso=2;
    array[3].peso=3;


    printf("First sort:\n");
    for(i=0; i<dim_aux; i++)
        printf("%d ",array[i].peso);

    printf("\n");


    qsort(array, dim_aux, sizeof(array[0]), comp);


    for(i=0; i<dim_aux; i++)
        printf("%d ",array[i].peso);

    printf("\n\n");

    array[4].peso=1;
    array[5].peso=5;
    array[6].peso=1;

    printf("Second sort:\n");


    for(i=0; i<dim; i++)
        printf("%d ",array[i].peso);

    printf("\n");

    qsort(array, dim, sizeof(array[0]), comp);

    for(i=0; i<dim; i++)
        printf("%d ",array[i].peso);




    printf("\n");

}

Моя комп функция:

int comp(const void* a, const void* b)
{
    aresta_* a1 = (aresta_*)a;
    aresta_* b1 = (aresta_*)b;
    return a1->peso > b1->peso;
}

Вывод:

First sort:
1 6 2 3 
1 2 3 6 

Second sort:
1 2 3 6 1 5 1 
6 2 3 1 1 5 1 
Program ended with exit code: 0

Где я ошибся? Любая помощь будет принята с благодарностью.


c sorting qsort
person Rui Loureiro    schedule 01.05.2017    source источник
comment
Ваша функция сравнения возвращает только 0 или 1, когда она должна возвращать положительное, отрицательное или ноль int.   -  person Weather Vane    schedule 01.05.2017
comment
@WeatherVane Вот и все. Поскольку это работало на первом сорте, я предположил, что ошибся где-то еще. Думаю, это не сработало, когда a==b. Большое тебе спасибо.   -  person Rui Loureiro    schedule 01.05.2017
comment
Вы можете return a1->peso - b1->peso;, но это может привести к арифметическому переполнению. Лучше привыкнуть к if(a1->peso > b1->peso) return 1; ... и т. д.   -  person Weather Vane    schedule 01.05.2017
comment
@WeatherVane Да, я выбрал вариант «если», и теперь он работает, как задумано. Спасибо еще раз.   -  person Rui Loureiro    schedule 01.05.2017
comment
@WeatherVane return a1->peso > b1->peso; точно такой же, как if(a1->peso > b1->peso) return 1 else return 0;   -  person 4386427    schedule 01.05.2017
comment
@ 4386427 нет, это не так. Я объясню вам ... в моем комментарии выше, который ОП прекрасно понял. if(a1->peso > b1->peso) return 1; if(a1->peso < b1->peso) return -1; return 0;   -  person Weather Vane    schedule 01.05.2017
comment
@ 4386427 есть три возможности, определенные требованиями к функции сравнения: a < b, a > b и a == b. Вы не можете получить три значения из одного сравнения.   -  person crashmstr    schedule 01.05.2017
comment
Однострочная функция сравнения 2-го класса: return (a<b) ? -1 : a > b;   -  person chux - Reinstate Monica    schedule 01.05.2017
comment
@chux тоже неплохо, но мой мозг по-прежнему предпочитает читать первое. Он ненавидит расшифровывать троичные вещи, что, я думаю, подрывает смысл языка программирования, обеспечивающего мост между тем, как мы думаем, и тем, как работают компьютеры. (Кроме того, я выбросил С++).   -  person Weather Vane    schedule 01.05.2017

Ответы (2)


arrow_upward
4
arrow_downward

Функция OP вернула только 0 и 1.

Поскольку это «сработало» для OP, для первых 4 значений это «удача».

Функция сравнения должна возвращать 1 из 3 результатов: отрицательный, 0 или положительный.

Функция должна возвращать целое число, меньшее, равное или большее нуля, если считается, что первый аргумент соответственно меньше, равен или больше второго.
C11dr §7.22.5.2 3

int comp(const void* a, const void* b)
{
    const aresta_* a1 = (const aresta_*)a;
    const aresta_* b1 = (const aresta_*)b;
    // return a1->peso > b1->peso;
    return (a1->peso > b1->peso) - (a1->peso < b1->peso);
}

return (a1->peso > b1->peso) - (a1->peso < b1->peso); имеет преимущества перед return a1->peso - b1->peso;. Этот ответ не переполняется. Это действительно и функционально правильно для всех пар int. Различные компиляторы распознают эту идиому и создают компактный код. int - int может переполняться, что является неопределенным поведением, UB.

person chux - Reinstate Monica    schedule 01.05.2017
comment
Примечание. Я предпочитаю const aresta_* aresta_*. Это позволяет избежать некоторых предупреждений компилятора, которые жалуются на отбрасывание const-ности const void*. - person chux - Reinstate Monica; 01.05.2017

arrow_upward
0
arrow_downward 

int comp(const void* a, const void* b)
{
    aresta_* a1 = (aresta_*)a;
    aresta_* b1 = (aresta_*)b;
    ---->   return a1->peso > b1->peso;  <---- Watch carefully out! What it does!
}

Обратная линия просто проверяет больше или нет. Если,

  • a1->peso больше, возвращает 1
  • b1->peso больше, возвращает 0 (Это тоже неверный результат, потому что ноль должен означать равенство)
  • Как насчет случая равенства, когда значения равны друг другу?

Вы не проверили последний случай. Для этого вы можете написать с такими случаями, как if-else

if(a1->peso > b1->peso) {
//  ....
} else if (a1->peso < b1->peso) {
// ....
} else {
// equality case....
}

или просто выполните return a1->peso - b1->peso, давая ожидаемый результат, который

  • > 0 такой позитивный
  • < 0 такой негатив
  • == 0 так равны друг другу

Согласно Чуксу, красиво обратившему внимание на точку переполнения, ее можно обработать в случае переполнения.

#include <limits.h>

if ((b1->peso > 0 && a1->peso < INT_MIN + b1->peso) ||
      (b1->peso < 0 && a1->peso > INT_MAX + b1->peso)) {
    /* Handle error */
} else {
    return a1->peso - b1->peso;
}
person snr    schedule 01.05.2017