Функция sort и алгоритмы сортировки [закрыт]

std::sort реализует один из алгоритмов сортировки (а иначе как отсортировать, если не использовать алгоритм сортировки).

Поэтому, правильно вопрос должен звучать где то так - алгоритм сортировки в std::sort хорош или нет? И ответ будет такой - в общем случае алгоритм std::sort достаточно хорош. Он обесчечивает n*ln(n) сложность.

Но очень часто нам известны некоторые характеристики сортируемого массива. И в этом случае самопальные алгоритмы могут оказаться сильно-сильно быстрее. К примеру, если массив уже почти отсортирован (всего 1-2 элемента не на своем месте) - в этом случае хорошо отработает обычный пузырек. Или массив состоит из однобайтовых чисел. В этом случае хорошо отработает сортировка подсчетом (за ленейное время).

И ещё один момент - сортировки бывают устойчивые и нет. Устойчивые сортировки сохранят относительный порядок одинаковых элементов. Если сортировать числа, то разницы нет, а вот если сложные объекты, то это может быть очень важно. std::sort реализует неустойчивую сортировку. А для устойчивой можно использовать stable_sort.

И последний момент - разные сортировки используют разный объем памяти. Пузырьку нужно всего два счетчика и одна переменная для обмена (но часто можно и без нее). А некоторым сортировкам нужны двукратные запасы. И если массив достаточно большой, то "быстрая сортировка" может быть не такой быстрой (память не безгранична, а своп - медленный). А пузырек потихоньку может и обогнать.

Библиотека C++ содержит целый ряд альгоритмов сортировки:

is_sorted  (C++11) 

проверяет, является ли диапазон отсортированым в порядке возрастания

is_sorted_until  (C++11) 

находит наибольший из отсортированых поддиапазонов

sort

сортирует диапазон в порядке возрастания

partial_sort 

сортирует первые N элементов в диапазоне

partial_sort_copy 

копирует и частично сортирует диапазон элементов

stable_sort 

сортирует диапазон элементов при сохранении порядка между равными элементами

nth_element 

помещает n-й элемент в позицию, которую он занимал бы после сортировки всего диапазона

В зависимости от задачи используйте один из этих альгоритмов. Все они работают максимально быстро, если правильно выбрать. Хотя могут быть случаи, когда простой альгоритм, написанным для конкретного тривиального случая, может оказаться быстрее...