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