Как все уже знают, в основу сортировки могут быть положены обмены, вставки, выбор, слияние и распределение.
Но если в алгоритме комбинируются разные методы, то тогда он относится к классу гибридных сортировок.Читать полностью »
Рубрика «сортировки»
Гибридные сортировки
2020-01-13 в 13:26, admin, рубрики: edisonsoftware, Алгоритмы, Блог компании Edison, визуализация данных, Программирование, Совершенный код, сортировкиСортировка «Американский флаг»
2019-12-29 в 22:58, admin, рубрики: edisonsoftware, python, Алгоритмы, Блог компании Edison, визуализация данных, Совершенный код, сортировки
Чтобы понять принцип действия этой «многополосной» сортировки проще для начала разобраться на примере флага с тремя полосами. А чтобы легко разобраться с трёхцветным флагом, лучше сначала посмотреть, как это работает на примере двухцветного. А чтобы разобраться с двухцветным...Читать полностью »
Подсчёт с приблизительным распределением — чаще всего переизобретаемая сортировка
2019-12-04 в 5:31, admin, рубрики: edisonsoftware, java, javascript, Алгоритмы, Блог компании Edison, Совершенный код, сортировки
Количество более-менее отличающихся друг от друга сортировок гарантированно более сотни. Среди них есть подгруппы алгоритмов, минимально отличающиеся друг от друга, совпадая в какой-то общей главной идее. Фактически в разные годы разными людьми придумываются заново одни и те же сортировки, различающихся в не слишком принципиальных деталях.
Чаще прочих встречается вот такая алгоритмическая идея.
Каждый элемент заносится примерно в то место массива, где он должен находиться. Получается почти упорядоченный массив. К которому или применяется сортировка вставками (она самая эффективная для обработки почти упорядоченных массивов) или локальные неупорядоченные области обрабатываются рекурсивно этим же алгоритмом.Читать полностью »
«5 копеек» к разговору о Cортировках
2019-09-30 в 11:00, admin, рубрики: C, c++, sort, sorting, Алгоритмы, высокая производительность, Программирование, сортировка, сортировкиВ продолжение темы хочу поделиться своим кодом, который обгоняет std::sort() из актуальных версий GNU C++ Library и (примерно, нет точных данных) повторяет результат "Сортировки Александреску" с CppCon 2019.
И ещё о сортировках
2019-09-15 в 18:04, admin, рубрики: boost, BSD, c++, processing, stl, Алгоритмы, алгоритмы сортировки, Программирование, сортировки, строки, структуры данныхИ ещё о сортировках
Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать полностью »
Сбалансированное слияние сверху-вниз и снизу-вверх
2018-12-10 в 10:14, admin, рубрики: C, edisonsoftware, Алгоритмы, Блог компании Edison, параллельное программирование, Программирование, сортировки
В прошлой статье мы ознакомились с реликтовыми сортировками слияния (вызывающих прежде всего исторический интерес). А что в тренде сегодня?Читать полностью »
Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных
2015-03-01 в 13:23, admin, рубрики: mail.ru, Алгоритмы, Блог компании ABBYY, Блог компании Mail.Ru Group, деревья, лекции технопарка, Программирование, сортировки, структуры данных, технопарк, хеш-таблицыОчередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.
Лекция 1. Основы
Начало первой лекции посвящено обсуждению основных понятий, на которых строится вся дальнейшая программа курса: что такое алгоритм и структура данных. Описаны базовые виды алгоритмов, их характеристики и методы анализа. Далее рассматриваются примеры создания алгоритмов для вычисления чисел Фибоначчи, проверки числа на простоту, быстрого возведения числа в целую степень. В конце лекции рассказывается об особенностях использования алгоритмов для работы с массивами: создание однопроходных алгоритмов, поиск минимального элемента, бинарный поиск.
Сортировка на односвязном списке за O(nlogn) времени в худшем случае с O(1) дополнительной памяти
2015-01-06 в 17:35, admin, рубрики: bfprt, flat quick sort, median of medians, Алгоритмы, итераторы, односвязные списки, сортировкиВсе началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:
- Время выполнения — гарантированные O(nlogn).
- Использование O(1) дополнительной памяти.
- Применимость для сортировки данных в односвязных списках.
Оговорки на все три ограничения:
- Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
- Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
- Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку).
Вся информация, которую мы знаем об элементах массива — это то, что они все образуют линейно упорядоченное множество. Все, что мы можем делать — это сравнивать два элемента массива и менять их местами.
Под катом можно узнать, что в итоге получилось у нас.
Challenge. Прежде чем заглядывать под кат, предлагаю сначала самостоятельно подумать над алгоритмом. Если придумается что-то круче нашего варианта — напишите в комментариях.
Глупая сортировка и некоторые другие, поумнее
2013-12-05 в 15:14, admin, рубрики: Алгоритмы, быстрая сортировка, пузырьковая сортировка, Совершенный код, сортировка, сортировка вставками, сортировки, Учебный процесс в IT, метки: быстрая сортировка, пузырьковая сортировка, сортировка, сортировка вставками, сортировки 
В прошлой статье мы оттолкнулись от так называемой глупой сортировки и путём нехитрых метаморфоз получили всем известную пузырьковую сортировку. Трансформируя последнюю пришли к целому вороху обменных способов упорядочивания массивов. Один из которых, между прочим, на структурах до нескольких тысяч элементов, даже работает быстрее чем быстрая сортировка.
Сегодня мы снова возьмём за основу stupid sort и внесём в неё другое маленькое, но существенное изменение. В результате получим совершенного другой эволюционный ряд сортировочных алгоритмов.
image: эволюция
Непрактичные сортировки – бессмысленные и беспощадные
2013-10-18 в 10:44, admin, рубрики: java, Алгоритмы, бабушкин, ненормальное программирование, сортировка, сортировки, метки: бабушкин, сортировка, сортировки 
А что это мы всё об умных да об эффективных алгоритмах? А давайте эту тоскливую осеннюю пятницу развеем чем-нибудь контрпродуктивным!?
Представляю Вашему вниманию ТОП-5 самых нетрадиционных сортировок всех времён и народов.
Младопрограммистам такое полезно показывать в дидактических целях. Всех остальных как минимум позабавит.
Читать полностью »