Сделать qsort стабильным, просто изменив сравнение?
Возможный дубликат:
Стабилизация стандартной библиотеки qsort?
Можно ли сделать qsort стабильным для ints, просто изменив мою операционную систему? Это мой код Я использую это на очень маленьких массивах размером около 5-7.
static int compare( const void *a, const void *b )
{
const int A(*(const int*)(a));
const int B(*(const int*)(b));
return B - A;
}
3 ответа
Если вы используете C++, функция stable_sort является стабильной и имеет производительность O(nlogn).
В противном случае быстрая сортировка на месте по своей природе нестабильна (я так считаю). Однако тривиальный вариант, использующий дополнительный массив для хранения информации, стабилен.
Я использовал по крайней мере одну версию qsort() это нестабильно, потому что однажды я обнаружил, что результат, производимый qsort() а также stable_sort() для случая ввода на моей машине были разные.
Вы не можете взять нестабильный алгоритм сортировки, такой как быстрая сортировка, и сделать его стабильным, просто изменив оператор сравнения. Вы должны начать со стабильного алгоритма сортировки, и тогда сравнение не имеет значения (если это строгий слабый порядок в C++).
Если массивы, которые вы сортируете, действительно настолько малы, то вам лучше использовать другой алгоритм сортировки. См., Например, ответы на: Быстрая стабильная сортировка для маленьких массивов (до 32 или 64 элементов) и Быстрая реализация алгоритма для сортировки очень маленького списка.