Из различных цитируемых источников я знаю, что встроенная функция C, stable_sort стабильна, но qsort нестабильна. Если это так, то почему мы вообще используем qsort? Разве это не лишнее? Почему бы вместо этого не использовать стабильную_сортировку?
В чем разница между встроенной функцией qsort и стабильной функцией сортировки?
Ответы (3)
Причиной выбора быстрой сортировки по сравнению со стабильной сортировкой в основном является скорость: qsort часто быстрее, чем stable_sort< /a>, что неудивительно, поскольку stable_sort имеет более сильную гарантию.
O(N·log2(N)). Если доступна дополнительная память, то сложность составляет O(N·log(N)).
Другим соображением является пространство: qsort выполняется на месте, что означает, что дополнительное выделение памяти не требуется. stable_sort, с другой стороны, пытается временно выделить размер, равный сортируемому массиву.
Эта функция пытается выделить временный буфер, равный по размеру сортируемой последовательности. Если выделение не удается, выбирается менее эффективный алгоритм.
Примечание из комментария rcgldr: (реализация HP/Microsoft std::stable_sort использует временный буфер 1/2 размера последовательности.Вторая половина сортируется во вторую половину последовательности, первая половина во временный буфер, затем временный буфер и вторая половина последовательности снова объединяются в последовательность.
person
Sergey Kalinichenko
schedule
21.09.2015
Реализация HP/Microsoft std::stable_sort использует временный буфер размером в 1/2 размера последовательности. Вторая половина сортируется во вторую половину последовательности, первая половина во временный буфер, затем временный буфер и вторая половина последовательности снова объединяются в последовательность.
- person rcgldr; 21.09.2015
@rcgldr Это очень умно с их стороны! Спасибо за примечание, я скопировал его в ответ.
- person Sergey Kalinichenko; 21.09.2015
HP/Microsoft std::stable_sort сначала сортирует первую половину, затем вторую половину, затем делается половинная копия во временный буфер и выполняется окончательное слияние (похоже, есть код для опционального обратного слияния (от последнего к первому), не уверен, используется ли это или остался лишний код). Я вспоминал оптимизированную версию этого, которая избегает дополнительных шагов копирования. Тем не менее ключевой идеей является использование временного буфера размером 1/2 размера последовательности.
- person rcgldr; 21.09.2015
Стабильная сортировка означает, что порядок одинаковых элементов сохраняется. Это не всегда требуется.
Если это не требуется, алгоритм проще, а иногда и быстрее и/или более эффективно использует память.
Типичным примером стабильного алгоритма сортировки является сортировка слиянием.
person
alain
schedule
21.09.2015
Если это так, то почему мы вообще используем qsort?
stable_sort() не является частью стандарта C. qsort() является частью стандарта C.
qsort() языка C не предназначен для использования алгоритма быстрой сортировки, не требует стабильности и не должен быть нестабильным.
qsort() часто используется, так как он самый портативный. Поскольку qsort() не имеет спецификаций, касающихся скорости, эффективности использования памяти и стабильности данных, он часто кодируется с использованием практичного метода для целевой платформы. На встроенной платформе объем памяти часто важнее скорости. На рабочем столе скорость, вероятно, имеет первостепенное значение.
person
chux - Reinstate Monica
schedule
21.09.2015
stable_sortтолько для С++. Он не является частью текущего стандарта C. - person Klas Lindbäck schedule 21.09.2015