Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Ещё одна сортировка разделением

Anna | 4.06.2014 | нет комментариев
Когда речь заходит об результативных алгорифмах сортировок, эрудированный програюзер сразу же припомнит неугасаемую «стремительную сортировку», новомодную «сортировку Тима», мифическую «сортировку слиянием» и даже мудрёную «интроспективную сортировку».

Не подвергая сомнению результативность вышеприведённых способов, предлагаю Вашему вниманию сортировку, которая при определённых входных данных легко уделывает по скорости всякий иной алгорифм.

Речь идёт о FlashSort, отлично обрабатывающей дюже крупные массивы с равномерно распределёнными данными.

Метод в 1998 году представил немецкий учёный Карл-Дитрих Нойберт. Его научная действие посвящена не столько теории алгорифмов, сколько физике твёрдого тела, биофизическим системам, физике элементарных частиц. Анализируя итоги экспериментов, Нойберт пришёл к итогу что крупные массивы статистических данных абсолютно разумно сортировать прибегнув к теории вероятностей.

Суть

Правило действия легко пояснить на определенном примере.

Представим, есть огромный массив размерности n, значения элементов которого варьируются в диапазоне от1 до 100. Если мы встречаем элемент со значением 50, то резонно предполагаем, что его законное место – посередине массива. Подобно обстоят дела и с другими элементами: 5, вероятно, должно находиться поближе к началу конструкции, 95 целесообразно задвинуть примерно в конец. В итоге таких небрежных манипуляций стремительно получим примерно отсортированный массив.

Перераскидав на скорую руку элементы, остаётся применить какой-нибудь способ, тот, что стремительно доупорядочивает недоупорядоченное (сортировка вставками абсолютно сгодится).

Матан

Основная задача сводится к тому, что все элементы массива в зависимости от их величин необходимо распределить по нескольким классам. Самые маленькие числа находятся в первом классе, самые крупные – в последнем, остальные числа – в промежуточных группах.

Если за число классов взять m, а также вестимы наименьший Amin и наивысший Amax элементы в массиве, то номер класса для элемента Ai вычисляется по дальнейшей формуле:

image

Квадратные скобки в выражении обозначают целую часть. Классы таким образом будут перенумерованы от 1до m. В дополнительном массиве Q[1..m] на позицию Q[K] заносится число элементов из основного массива, принадлежащих соответствующему классу.

После этого, применяя добавочный массив, перераспределяем элементы основного массива, вставляя их напримерно свои места. Алгоритмические нюансы – в коде java-программы приведённой ниже.

Визуализация

GIF-анимация, продолжительность больше 2-х минут. Станет ясно, отчего сортировку окрестили «мелькающей».

image

Результативность по времени

Как теснее упоминалось, алгорифм крайне результативен на крупных массивах с равномерно распределёнными данными. В этом случае FlashSort со средней временной трудностью O(n) значительно опережает иQuickSort и прочие результативные способы сортировок.

В остальных обстановках дела не столь блестящs_rqvmk!
Код взят отсель, комментарии мои.
Коллекцию реализаций на разных ЯП (Ада, Си, Бейсик, Форт, Фортран, Ява, Паскаль) дозволено найти на сайте академика.

Колляции алгорифма

Наименование FlashSort (Мелькающая сортировка; Проблесковая сортировка)
Автор Карл-Дитрих Нойберт
Год публикации 1998
Класс Сортировка разделением
Устойчивость Нестабильная
Сопоставления Без сопоставлений
Временная трудность худшая O(n2)
средняя O(n m)
лучшая O(n)
Трудность по памяти каждого O(n m)
добавочные данные O(m)

Ссылки

FlashSort в английской Википедии
Карл-Дитрих Нойберт, персональный сайт.
FlashSort на Dr. Dobb’s Journal
Java-визуализация

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB