Комментарии 19
Скорее это эвристика к какому-нибудь основному алгоритму. Вырожденный случай — сортировка подсчетом.
Более надёжный метод — поразрядная сортировка. Классы предопределены заранее, за один проход считаем мощность классов, за другой — ставим классы на места. Дальше рекурсия. От равномерности распределения сложность почти не зависит.
Если знать исходное распределение, то и quicksort заработает быстрее, ведь там опорный элемент в идеале должен являться медианой. Тогда зачем еще один алгоритм.
Основная проблема чисто конструктивная. Все привыкли, что функции сортировки делают все сами, а в данном случае надо как то описывать распределение, границы значений.
В каком то узком спец софте, возможно стоит заморочиться.
Основная проблема чисто конструктивная. Все привыкли, что функции сортировки делают все сами, а в данном случае надо как то описывать распределение, границы значений.
В каком то узком спец софте, возможно стоит заморочиться.
Quicksort никак не удастся заставить работать быстрее, чем за O(n*log(n)). А зная место элемента, мы можем приблизить скорость к O(n) — чем точнее знаем место, тем лучше получится.
Даже если Quicksort будет знать исходное распределение, то быстрее не заработает.
Основа Quicksort — это random shuffle в самом начале. А затем идет секционирование и сама сортировка.
Shuffle нужен для вероятностной гарантии того, что секционирование пройдет правильно.
Без «перетасовки» можно нарваться на производительность O(N^2) — это худший случай для Quicksort.
А в лучшем случае, как уже сказали, Quicksort имеет O(N*lg(N)) и никак не меньше.
Основа Quicksort — это random shuffle в самом начале. А затем идет секционирование и сама сортировка.
Shuffle нужен для вероятностной гарантии того, что секционирование пройдет правильно.
Без «перетасовки» можно нарваться на производительность O(N^2) — это худший случай для Quicksort.
А в лучшем случае, как уже сказали, Quicksort имеет O(N*lg(N)) и никак не меньше.
Стабильность: Нестабильная
Мне кажется все же это называется устойчивость сортировки, а «стабильность» — калька с английского.
«Стабільність покращено» (полит.-укр.). Дельное замечание, спасибо. Подправил.
Я ещё размышляю над другим моментом. В результате FlashSort элементы попадают на примерно свои позиции, которые, при необходимости корректируются сортировкой вставками. Спорный вопрос, является ли FlashSort устойчивой или неустойчивой сортировкой, скорее речь идёт о некой "условной устойчивости" или "частичной устойчивости", если, конечно, в теории алгоритмов есть такие понятия.
Я ещё размышляю над другим моментом. В результате FlashSort элементы попадают на примерно свои позиции, которые, при необходимости корректируются сортировкой вставками. Спорный вопрос, является ли FlashSort устойчивой или неустойчивой сортировкой, скорее речь идёт о некой "условной устойчивости" или "частичной устойчивости", если, конечно, в теории алгоритмов есть такие понятия.
GIF-анимация, длительность более 2-х минут
Мсье знает толк…
137 кадров )))
Способ приготовления следующий: алгоритм реализуется в Excel с помощью макросов VBA, каждый шаг экспортируется в изображения. Потом быстренько их сцепляем в анимацию. )))
Я так уже нарисовал почти три десятка сортировок, недавно скатерть Улама симпатично получилась. Статьи про алгоритмы с «мультиками» ещё будут, идей много, реализация поставлена на поток. )))
Способ приготовления следующий: алгоритм реализуется в Excel с помощью макросов VBA, каждый шаг экспортируется в изображения. Потом быстренько их сцепляем в анимацию. )))
Я так уже нарисовал почти три десятка сортировок, недавно скатерть Улама симпатично получилась. Статьи про алгоритмы с «мультиками» ещё будут, идей много, реализация поставлена на поток. )))
Уважаю, труд немалый.
А если сделать еще один шаг, то станет вообще шикарно, а именно — перевести в видео и, например, залить на youtube
(Сделать такое можно с помощью www.virtualdub.org — открыть гифку и сохранить как .avi, дальше — ясно).
Просматривать так будет намного удобнее — можно будет поставить на паузу и потупить, потому что гифка не оставляет шансов, приходится очень быстро думать :)
А если сделать еще один шаг, то станет вообще шикарно, а именно — перевести в видео и, например, залить на youtube
(Сделать такое можно с помощью www.virtualdub.org — открыть гифку и сохранить как .avi, дальше — ясно).
Просматривать так будет намного удобнее — можно будет поставить на паузу и потупить, потому что гифка не оставляет шансов, приходится очень быстро думать :)
По-моему хабрастораж эту анимацию съел…
А можно ссылку на формальное доказательство того, что мы можем приблизится к O(n)?
Есть doc-документ за авторством самого Нойберта, где он даёт разъяснения по поводу алгоритма. Я не силён в английском, по поводу временной сложности там вроде обоснование есть.
Почему-то до сих пор нет комментария о том, что m и n неспроста связаны именно таким коэффициентом.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Ещё одна сортировка распределением