Comments 19
Скорее это эвристика к какому-нибудь основному алгоритму. Вырожденный случай — сортировка подсчетом.
Более надёжный метод — поразрядная сортировка. Классы предопределены заранее, за один проход считаем мощность классов, за другой — ставим классы на места. Дальше рекурсия. От равномерности распределения сложность почти не зависит.
Если знать исходное распределение, то и quicksort заработает быстрее, ведь там опорный элемент в идеале должен являться медианой. Тогда зачем еще один алгоритм.
Основная проблема чисто конструктивная. Все привыкли, что функции сортировки делают все сами, а в данном случае надо как то описывать распределение, границы значений.
В каком то узком спец софте, возможно стоит заморочиться.
Quicksort никак не удастся заставить работать быстрее, чем за O(n*log(n)). А зная место элемента, мы можем приблизить скорость к O(n) — чем точнее знаем место, тем лучше получится.
Даже если Quicksort будет знать исходное распределение, то быстрее не заработает.

Основа Quicksort — это random shuffle в самом начале. А затем идет секционирование и сама сортировка.
Shuffle нужен для вероятностной гарантии того, что секционирование пройдет правильно.
Без «перетасовки» можно нарваться на производительность O(N^2) — это худший случай для Quicksort.

А в лучшем случае, как уже сказали, Quicksort имеет O(N*lg(N)) и никак не меньше.
С перетасовкой тоже можно попасть на N^2 — если неудачно перетасовать. И на N — если удачно.
А наивный квиксорт не предполагает сортировку. Просто кандидата в медианы берёт из первой позиции.
Перетасовка, на самом деле, несущественна. Достаточно брать кандидата из позиции наугад.
Стабильность: Нестабильная


Мне кажется все же это называется устойчивость сортировки, а «стабильность» — калька с английского.
«Стабільність покращено» (полит.-укр.). Дельное замечание, спасибо. Подправил.

Я ещё размышляю над другим моментом. В результате FlashSort элементы попадают на примерно свои позиции, которые, при необходимости корректируются сортировкой вставками. Спорный вопрос, является ли FlashSort устойчивой или неустойчивой сортировкой, скорее речь идёт о некой "условной устойчивости" или "частичной устойчивости", если, конечно, в теории алгоритмов есть такие понятия.

GIF-анимация, длительность более 2-х минут

Мсье знает толк…
137 кадров )))

Способ приготовления следующий: алгоритм реализуется в Excel с помощью макросов VBA, каждый шаг экспортируется в изображения. Потом быстренько их сцепляем в анимацию. )))

Я так уже нарисовал почти три десятка сортировок, недавно скатерть Улама симпатично получилась. Статьи про алгоритмы с «мультиками» ещё будут, идей много, реализация поставлена на поток. )))
Уважаю, труд немалый.
А если сделать еще один шаг, то станет вообще шикарно, а именно — перевести в видео и, например, залить на youtube
(Сделать такое можно с помощью www.virtualdub.org — открыть гифку и сохранить как .avi, дальше — ясно).
Просматривать так будет намного удобнее — можно будет поставить на паузу и потупить, потому что гифка не оставляет шансов, приходится очень быстро думать :)
Ваша правда. Залил на Ютуб, видео в статье находится в разделе «Визуализация».
Видимо, это была какая-то особенность кэширования. Сейчас переоткрыл — всё замелькало.
А можно ссылку на формальное доказательство того, что мы можем приблизится к O(n)?
Есть doc-документ за авторством самого Нойберта, где он даёт разъяснения по поводу алгоритма. Я не силён в английском, по поводу временной сложности там вроде обоснование есть.
Почему-то до сих пор нет комментария о том, что m и n неспроста связаны именно таким коэффициентом.
Only those users with full accounts are able to leave comments. Log in, please.