Комментарии 9
Не соглашусь с оценкой, что по быстроте один из самых быстрых. да, может быть Нотация Big O для Timsort O(n log n), но эта нотация говорит только о поверхностном анализе. Детали кроятся в другом.
Если речь идёт о числах, то алгоритму Countingsort нет равных. Если речь идёт об строковых значениях, то в алгоритме Timsort элементы перставляются очень большое (из перспектив других алгоритмов - ненужное) количество раз, если изначальная ситуация значений из average case/worst case. А перестановка строк - очень интенсивная операция. Сравнение тоже, но если не обращать внимание на усилия по перестановки, то можно быстро получить сюрпризы по скорости выполнения, когда задача будет отсортировать не десять значений, а например 1 миллион.
И хоть сортировка неплохая, но всё равно - заголовк не соответствует содержанию.
Прошу прощения, но разве перестановка указателей/ссылок на строки чем-то кардинально отличается от перестановки чисел? Честно говоря, ни разу в реальных проектах не видел такого, чтобы в массив пихали прям массивы символов - обычно это указатели (в случае C++, если использовать std::string - у него под капотом тоже указатель, std::move поможет избавиться от излишнего копирования) или ссылки (в случае управляемых языков, таких например как C#). Размер указателя/ссылки в зависимости от платформы равен 4 или 8 байт (если говорить про x86/x64), т. е. должен влезать в регистры процессора - то есть, никакого overhead не должно быть.
Если речь идёт о числах, то алгоритму Countingsort нет равных.
Вот только это не специализированный алгоритм, поэтому сравнение некорректно.
Если речь идёт об строковых значениях, то в алгоритме Timsort элементы перставляются очень большое
Не больше, чем O(n log n).
А перестановка строк — очень интенсивная операция.
Нет, для всех известных мне языков это обмен двух указателей, ничем не отличается от общего случая.
И хоть сортировка неплохая, но всё равно — заголовк не соответствует содержанию.
Назовите более быстрый алгоритм сортировки общего назначения (т.е. для comparative sort).
Про перестановку - соглашусь. Но Ваше первое и последнее заявления не разделяю.
В название сказано - самый быстрый алгоритм. Там ничего не сказано про "должен он быть общего назначения". И не знаю как у других, но я сортирую больше всего числа. Поэтому и беру для этого Countingsort, т.к. разница по скорости сортировки даже с Timsort раз в 10. И для многих, кто впервые сталкивается с таким заголовком - начинают верить, что оно так и есть.
И не понимаю, в чём Вы не согласны с моим выражением " заголовок и правда не соответствует содержанию". Если заголовок уточнить условиями, которые описали Вы, то да, мой пример не подходил-бы. Не люблю, когда неточно выражаются, а потом это приводит к непониманию - "иди, мол сделай вон то и не делай вид, что не понимаешь..."
И какой, по-вашему, лучший алгоритм для сортировки строк? Просто ради интереса спрашиваю
Затем Timsort переходит в режим galloping. Вместо того чтобы сверять A[0] и B[0] друг с другом, Timsort выполняет бинарный поиск соответствующей позиции b[0] в a[0].
Стоит заметить, что именно это и убирает log(n) из стандартного n*log(n) для лучшего случая.
Timsort — самый быстрый алгоритм сортировки, о котором вы никогда не слышали
А если слышали (только на хабре 4 статьи)?
Timsort: Очень быстрый, O(n log n), стабильный алгоритм сортировки, созданный для реального мира, а не для академических целей.
А какой из алгоритмов, кроме шуточных типа randomsort, создан для академических целей?
Я понимаю, что перевод, но сохранять все эти загибы автора как-то мало смысла.
Алгоритм, по сути — сортировка слиянием с некоторыми эвристиками для более быстрой работы в некоторых случаях.
Ту же ассимптотическую сложность можно получить, например, просто проверив, что массив изначально отсортирован и не делать дальше ничего, а в противном случае запускать стандартный merge-сорт.
Вот что было бы интереснее, это сравнение разных реализаций сортировок на каких-то реальных данных.
Про TimSort не знает только тот, кто не задавался вопросом как работает sorted() и sort() в Python. Он основывается на предположение того, что большинство массивов уже предварительно частично упорядочены. Логика работы TimSort на самом деле довольно прозрачная:
•TimSort делит входной массив на подмассивы;
•Сортирует подмассивы вставками;
•Объединяет их попарно сортировкой слиянием;
•И возвращает отсортированный массив.
Один из примеров на YouTube https://www.youtube.com/watch?v=NVIjHj-lrT4
Timsort — самый быстрый алгоритм сортировки, о котором вы никогда не слышали