Pull to refresh

Comments 8

сортируем его вставками. Почему вставками? Просто на практике выяснилось, что для небольших массивов он лучше любых логарифмических сортировок

а теперь взгляните на DerSort: он быстрее сортировки вставками, и деален в обе стороны!

https://ders.by/alg/dersort/dersort.html

Я за вас уже сходил по ссылке, не тратьте время: тут полная клиническая картина: название алгоритма по своему имени, историческая справка, кривое объясниение и ошибочная оценка времени работы. Карма у автора соответствующая.

И тем не менее используемая в питоне сортировка тоже названа именем автора. Прогнал код на случайных данных, действительно вызовов компаратора меньше, чем у std::sort.

В сортировке подсчетом или RadixSort этих сравнений вообще 0 будет. Количество сравнений элементов - не главный критерий.

Вообще, это тривиальная и совсем не новая идея: в сортировке вставками можно искать место вставки бинарным поиском. Ведь там надо в уже отсортированном массиве найти это место. У товарища фактически это и есть, только вывернуто наизнанку с массивом перестановок вместо изменения самого массива, кривовато написано, и ужасно объяснено.

На практике этого нигде не делают, потому что получается медленнее. Ведь помимо поиска места надо еще элементы сдвинуть, так что можно в качестве условия цикла, которое все-равно будет, использовать сравнение чисел. Само сравнение - это фактически одно вычитание в процессоре - это очень быстро. Медленно происходят условные переходы, а их бинарный поиск только сверху добавляет. Плюс нелокальность доступа к памяти дополнительно тормозит работу.

Если же сортируются сложные объекты, и их сравнение - тяжелая операция, то тут уже любой quicksort оказывается быстрее квадратичных сортировок даже для совсем маленьких массивов.

Обратите внимание, автор лишь сравнил количество сравнений и даже нигде не сравнил собственно производительность своего детища.

используемая в питоне сортировка тоже названа именем автора

Тим Петерс сначала много лет пилил питон, написал "библию" питонистов и зарекомендовал себя. Только потом уже давно используемую сортировку стали называть в его честь. Сам он ее назвал listsort.

У Александреску кажется на эту тему было выступление. У бинарного поиска (на 14:30 в видео) встроенного в сортировку высокая энтропия, предсказатель переходов на каждом шаге угадывает с вероятностью 50%. В отличие от линейного поиска, где после разгона ошибка всего одна и в конце. В итоге с бинарным поиском сравнений меньше, а время выполнения все равно вышло больше, причем на миллионе случайных double.

синим обозначается публичная информацию, красным - секретная):

... Далее следует зелёный и голубой текст... хм, ладно

Sign up to leave a comment.

Articles