Комментарии 11
Стабильность. алгоритм сортировки называется стабильным, если он сохраняет относительный порядок одинаковых элементов.
Господи, кто вам это начитывал? Это называется "устойчивая", а вовсе даже не "стабильная".
Быстрая сортировка
Самая быстрая на практике.
Да вряд ли. Есть поразрядная и подсчётом - они побыстрее будут.
PS. Жаль, что в рассмотрение не включена сортировка кучей (Heap Sort). У неё единственный минус по сравнению с рассмотренными методами (точнее, только с одним из двух) - отсутствие устойчивости. Зато всё остальное - плюсы.
А ещё пирамидальная сортировка не паралелится и не работает на списках последовательного доступа. По сути - улучшенный пузырьковый алгоритм. Любую "кучу" данных захочется сначала упорядочить или проиндексировать.
Настоящий квиксорт на массиве - тоже неустойчивый.
Минус пирамидальной сортировки - в том, что она в лучшем случае вдвое медленнее быстрой (элементы сравниваются и перемещаются дважды - при сборке и разборке кучи).
А вот плюс - в том, что она гарантирует логлинейное время.
Промышленные методы сортировки - это сплав быстрой, вставок и пирамиды.
если массив маленький, то вставками он сортируется быстрее, просто потому, что два цикла быстрее, чем рекурсии
если глубина рекурсии превысила порог, кратный логарифму длины массива, это признак того, что набор плохой для квиксорта, и надо валить оттуда, пока мы до квадрата не доигрались, - запускают пирамиду
в лучшем случае вдвое медленнее быстрой
Это как? Если Вы взялись сравнивать два O(nlogn), то уж точно не с такой аргументацией. Быстрая сортировка в среднем делает nln(n) сравнений (обычно в анализе приводят 2n(ln), как например тут, но там алгоритм разделения предполагает n сравнений на n элементов в то время как обычно используется алгоритм с n/2 сравнений. С пирамидальной сортировкой сложнее, потому что худший случай -- это когда во всех операциях новый/удаляемый элемент проходит полностью путь от корня до листа и наоборот, но даже тут есть нюанс, заключающийся в том, что размер кучи равномерно изменяется от 1 к n и обратно, что ведет к n(log_2(n)-2), в среднем случае как будто получается nlog_2(n) (не проверял) и разница соответственно уже на в два раза, а ln(2). Короче я это к тому, что стоит вкидывать не совсем верные утверждения без должного подкрепления где это можно детально посмотреть.
Промышленные методы сортировки - это сплав быстрой, вставок и пирамиды
Ну что за недосказанность! Это описание сортировки introsort, используемой например в качестве std::sort в gcc c неочевидной реализацией перехода на вставки для массивов длины 16. Стоит отметить, что все три используемых вспомогательных сортировок (быстрая, пирамидальная, вставками) -- inplace для массивов.
А почему в примере реализации quicksort на питоне используются дополнительные массивы вместо in place варианта?
Сортировка слиянием сама по себе не требует дополнительной памяти. Всё зависит от используемой структуры данных.
Также сортировка слиянием лучше распараллеливается, чем быстрая сортировка.
А ещё у разных алгоритмов разный расход памяти. Очень зря Вы об этом не написали в смысле какой алгоритм сколько потребляет. Когда нужно реализовать сортировку на mcu, и у вас на всё про всё, например, 256 байт памяти, это имеет первостепенное значение.
Странно, что не разобран TimSort который является дефолтным в Java и в Python.
Это база. Алгоритмы сортировки для начинающих