Нет необходимости указывать на то, что функция сравнения в OP некорректна, и ее использование - неопределенное поведение. Тем не менее, интересно спросить, как это могло бы работать.
Хотя для интерфейса qsort требуется функция компаратора, которая возвращает целое число, обеспечивающее три возможных возвращаемых значения, ничто не обязывает реализацию qsort использовать всю эту информацию. Он всегда может выполнять одну и ту же простую двустороннюю ветвь. Это было бы похоже на функцию sort стандартной библиотеки C ++ , компаратор которой возвращает логическое значение true, если первый аргумент строго меньше второго аргумента.
Конечно, функция сравнения вашего студента никогда не будет указывать, что первый аргумент строго меньше, чем второй аргумент, что создаст проблемы для реализации, в которой тесты будут выглядеть примерно так:
if (*cmp(p, q) < 0) ...
Однако, если компаратор всегда вызывается как:
if (*cmp(p, q) > 0) ...
(или, что эквивалентно, <=), тогда компаратор вашего студента будет работать без проблем.
Поскольку glibc является открытым исходным кодом, это легко проверить, как только мы найдем правильную функцию сортировки. Но не все так, как кажется. Существует исходный файл с именем qsort.c (в каталоге stdlib), который реализует алгоритм быстрой сортировки (, а не алгоритм интросорта, используемый большинством современных реализаций std::sort), и в этом файле мы можем увидеть последовательное использование строгого меньше, чем. Например, из основного внутреннего цикла :
while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
left_ptr += size;
while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
right_ptr -= size;
(В функции есть много других сравнений, но все они имеют одинаковую форму.)
Так что это не должно работать вообще с компаратором вашего студента. Однако оказывается, что эта функция обычно не вызывается qsort. qsort фактически определено в файле msort.c, который реализует сортировку слиянием. А функция сортировки слиянием выполняет тесты «меньше или равно». Например:
if ((*cmp) (b1, b2, arg) <= 0)
Реализация сортировки слиянием не на месте, что будет медленнее; это требует временной памяти. И это может быть проблемой, потому что qsort должно работать, даже если временная память не доступна. Таким образом, фактическая реализация qsort начинается с попытки выяснить, достаточно ли физической памяти. (Требуется физическая память, а не пространство подкачки, чтобы избежать подкачки. Также помните, что Linux выполняет оптимистичное распределение, так что тот факт, что malloc завершается успешно, не обязательно означает, что выделенные адреса виртуальной памяти действительно могут использоваться.) Здесь он вычислил необходимое временное пространство (в size) и sysconf, чтобы узнать, сколько физической памяти имеет хост. (Он делит это значение на четыре, чтобы не занимать всю физическую память.)
/* If the memory requirements are too high don't allocate memory. */
if (size / pagesize > (size_t) phys_pages)
{
_quicksort (b, n, s, cmp, arg);
return;
}
Таким образом, если сортировка слиянием потребует слишком много памяти, она откладывается до _quicksort, что является именно той функцией, из которой я цитировал ранее, в qsort.c.
В итоге:
Неисправная функция компаратора будет работать с реализацией qsort в glibc при условии, что сортируемый массив не слишком велик.
Если массив слишком большой, сортировка не удастся.
В отличие от этого, реализация BSD qsort использует все три возвращаемых значения компаратора. В его внутреннем цикле мы видим:
while (pb <= pc && (cmp_result = CMP(thunk, pb, a)) <= 0) {
if (cmp_result == 0) {
swap_cnt = 1;
swap(pa, pb);
pa += es;
}
pb += es;
}
while (pb <= pc && (cmp_result = CMP(thunk, pc, a)) >= 0) {
if (cmp_result == 0) {
swap_cnt = 1;
swap(pc, pd);
pd -= es;
}
pc -= es;
}
Есть также звонки компаратору, чтобы найти точку опоры; Это все формы <, поэтому они также дадут неправильный ответ. Однако не все потеряно; для очень маленьких векторов (менее семи элементов) вместо этого используется сортировка вставкой, а в цикле сортировки вставки используется более строгое сравнение.