Рубрика «алгоритмы сортировки»

Иллюстрация SAPT Adobe Photoshop

Иллюстрация SAPT Adobe Photoshop

Отчет о, написанном мною, алгоритмическом статичном двунаправленном дереве, имеющим сложность O(1)Читать полностью »

Сортировка — это процесс упорядочивания элементов в массиве или списке по определенному критерию (например, по возрастанию или убыванию). В программировании это одна из базовых задач, которая помогает эффективно искать, обрабатывать и анализировать данные. Давайте разберем основные алгоритмы сортировки, их принципы работы и сложность на примерах реализации на языке Go.


Введение в алгоритмы сортировки

Существует несколько способов сортировки данных. Основные алгоритмы можно разделить на две категории:

  1. Простые алгоритмы сортировкиЧитать полностью »

Сортировка «Милосердный Сталин» - 1


Merciful Stalin Sort (сортировка «Милосердный Сталин») — это новый алгоритм сортировки, вдохновлённый пресловутым Stalin Sort (сталинской сортировкой). В ходе развлекательного эксперимента со сталинской сортировкой возникла интригующая идея: что, если вместо удаления выбивающихся элементов, сохранить те, которые идут по порядку, и рекурсивно упорядочить остальные? Логика заключалась в том, чтобы добиться повышения производительности за счёт уменьшения массива, требующего сортировки, особенно в случае частично упорядоченных массивов. Это и привело к разработке сортировки «Милосердный Сталин».Читать полностью »

Как посчитать биологические данные и не уронить сервер и ноутбук? - 1

Привет, Хабр


Наверняка вы слышали о биоинформатике. Звучит перспективно, приятно и полезно. Часто, ввиду всеобщих рассказов о перспективности и возможностях направления, некоторые люди из IT или из «мокрой» биологии (так называют область биологии, где работают в лаборатории с бактериями и прочими возможными объектами живой и не очень природы и реагентами) хотят перейти в биоинформатику. Однако далеко не все понимают, что же это за область такая и почему с ней сложно работать.Читать полностью »

imageМногие программисты думают, что Quick Sort — самый быстрый алгоритм из всех существующих. Отчасти это так. Но работает она действительно хорошо только если правильно выбран опорный элемент (тогда сложность составляет O (n log n)). В противном же случае асимптотика будет примерно такой же как и в пузырика (то-есть O (n2)).
При этом, если массив уже отсортирован, то алгоритм всё-равно будет работать не быстрее, чем за O (n log n)

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

«Дело было вечером, делать было нечего», — Сергей Михалков.

Требования:

  1. Лучший случай O (n)
  2. Средний случай O (n log n)
  3. Худший случай O (n log n)
  4. В среднем быстрее быстрой сортировки

А теперь давайте обо всём по порядку

Чтобы наш алгоритм всегда работал быстро, нужно чтобы в среднем случае асимптотика была хотя бы O (n log n), а в лучшем — O (n). Все мы прекрасно знаем, что в лучшем случае сортировка вставками работает за один проход. Но в худшем ей придётся гонять по массиву столько раз, сколько в нём элементов.

Читать полностью »

И ещё о сортировках

Рискну опять поднять эту тему. Начну со ссылки на статью Михаила Опанасенко (oms7), очень впечатляющую по объёмам проделанной работы, а также по количеству приведёных ссылок. Свой материал начал готовить, не зная об этой публикации, что впоследствии, после ознакомления привело к необходимости его существенной переработки. Для тех, кто уже прочитал эту статью, сообщаю, что в моём материале, исследуются более разнообразные по типам данные, в частности, строки и вещественные числа, используются библиотеки boost и bsd, а также затрагиваются некоторые другие отсутствующие в названной статье темы.
Читать полностью »

Сортировки выбором - 1

В чём идея сортировок выбором?

  1. В неотсортированном подмассиве ищется локальный максимум (минимум).
  2. Найденный максимум (минимум) меняется местами с последним (первым) элементом в подмассиве.
  3. Если в массиве остались неотсортированные подмассивы — смотри пункт 1.

Читать полностью »

Три дня назад я задумался об объединении сортировки подсчётом и деревом. Обсудив её с коллегой, пришли к следующему решению: вместо TreeSet использовать HashMap (при чём здесь вообще TreeSet, можно посмотреть ниже). Но и этого мне показалось мало, так что я решил реализовать собственную хэш-таблицу и посмотреть, что из этого выйдет. Результаты показались мне довольно интересными интересными.
Читать полностью »

Сортировки вставками - 1

Общая суть сортировок вставками такова:

  1. Перебираются элементы в неотсортированной части массива.
  2. Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться.

Читать полностью »

Сравнение сортировок обменами - 1

Сферические алгоритмы в вакууме — это прекрасно. Однако давайте спустимся с небес на грешную землю и посмотрим как вся эта теоретическая красота покажет себя на практике.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js