Comments 8
сортируем его вставками. Почему вставками? Просто на практике выяснилось, что для небольших массивов он лучше любых логарифмических сортировок
а теперь взгляните на DerSort: он быстрее сортировки вставками, и деален в обе стороны!
Я за вас уже сходил по ссылке, не тратьте время: тут полная клиническая картина: название алгоритма по своему имени, историческая справка, кривое объясниение и ошибочная оценка времени работы. Карма у автора соответствующая.
И тем не менее используемая в питоне сортировка тоже названа именем автора. Прогнал код на случайных данных, действительно вызовов компаратора меньше, чем у std::sort.
В сортировке подсчетом или RadixSort этих сравнений вообще 0 будет. Количество сравнений элементов - не главный критерий.
Вообще, это тривиальная и совсем не новая идея: в сортировке вставками можно искать место вставки бинарным поиском. Ведь там надо в уже отсортированном массиве найти это место. У товарища фактически это и есть, только вывернуто наизнанку с массивом перестановок вместо изменения самого массива, кривовато написано, и ужасно объяснено.
На практике этого нигде не делают, потому что получается медленнее. Ведь помимо поиска места надо еще элементы сдвинуть, так что можно в качестве условия цикла, которое все-равно будет, использовать сравнение чисел. Само сравнение - это фактически одно вычитание в процессоре - это очень быстро. Медленно происходят условные переходы, а их бинарный поиск только сверху добавляет. Плюс нелокальность доступа к памяти дополнительно тормозит работу.
Если же сортируются сложные объекты, и их сравнение - тяжелая операция, то тут уже любой quicksort оказывается быстрее квадратичных сортировок даже для совсем маленьких массивов.
Обратите внимание, автор лишь сравнил количество сравнений и даже нигде не сравнил собственно производительность своего детища.
используемая в питоне сортировка тоже названа именем автора
Тим Петерс сначала много лет пилил питон, написал "библию" питонистов и зарекомендовал себя. Только потом уже давно используемую сортировку стали называть в его честь. Сам он ее назвал listsort.
У Александреску кажется на эту тему было выступление. У бинарного поиска (на 14:30 в видео) встроенного в сортировку высокая энтропия, предсказатель переходов на каждом шаге угадывает с вероятностью 50%. В отличие от линейного поиска, где после разгона ошибка всего одна и в конце. В итоге с бинарным поиском сравнений меньше, а время выполнения все равно вышло больше, причем на миллионе случайных double.
классный троллинг!
спасибо
синим обозначается публичная информацию, красным - секретная):
... Далее следует зелёный и голубой текст... хм, ладно
Лучшие алгоритмы 20 века по версии SIAM