Почему функция сравнения, переданная qsort (), должна возвращать три разных значения?

Question

Я прочитал, что функция сравнения, требуемая qsort(), должна иметь 3 результата:

• отрицательный результат, если val1 < val2
• 0, если val1 == val2
• положительный результат, если val1 > val2

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

int compare(int a, int b)
{
    if(a>b) return 1;
    return 0;
}
void bubbleSort(int arr[], int n) 
{
    int i, j;
    for (i = 0; i < n-1; i++)  
        for (j = 0; j < n-i-1; j++)  
            if ( compare(arr[j],arr[j+1]) ) 
                swap(&arr[j], &arr[j+1]);
}

Так почему функция сравнения qsort() должна иметь 3 возможных результата, а не 2?

Answer 1

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

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

Answer 2

Если внутренний цикл быстрой сортировки записан эквивалентно этому:

while(x[i] < pivot) i++;  // less-than
while(pivot < x[j]) j--;  // less-than

, тогда вы можете обойтись только с реализацией <.

В любом случае, придерживайтесь принципа наименьшего удивления , делая более очевидным, что должен делать вызывающий объект - если указатель функции сравнения называется compare и функцияне должен вести себя как обычный stdlib qsort сравнить делегат, тогда это плохая идея.

С другой стороны, если ваш параметр назван как-то вроде less_than или isLessThan, для вызывающей стороны должно быть гораздо более очевидно, что ожидается от функции сравнения:

 void sort(
     const void * arr,
     size_t num_items,
     size_t element_size, 
     bool (*is_less_than)(const void*, const void*)
 );

Answer 3

Если элемент A == элемент B, но функция компаратора сообщает qsort, что B > A, тогда qsort будет думать, что могут быть другие элементы, которые должны быть между A и B, если это неи, следовательно, выполнить ненужные проверки.

Answer 4

Технически, вы можете сделать только с меньшим, чем, потому что a == b эквивалентно !(a < b) && !(b < a).

Answer 5

Исходя из комментария @Matteo Italia, существует проблема эффективности числа сравнений, и вы можете уменьшить число сравнений, используя равенство, так как a == b и !(a < b) && !(b < a) эквивалентны в некоторых случаях (например, когдазначения целочисленные).

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