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

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

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

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

Если описать в паре предложений по какому принципу работают сортировки обменами, то:

  1. Попарно сравниваются элементы массива
  2. Если элемент слева* больше элемента справа, то элементы меняются местами
  3. Повторяем пункты 1-2 до тех пор, пока массив не отсортируется

* — под элементом слева подразумевается тот элемент из сравниваемой пары, который находится ближе к левому краю массива. Соответственно, элемент справа находится ближе к правому краю.
Читать полностью »

80+ алгоритмов сортировки

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

Параллельная сортировка данных в GPU - 1

В этой статье я познакомлю вас с концепцией параллельной сортировки. Мы обсудим теорию и реализацию шейдера, сортирующего пиксели.

GIF

Параллельная сортировка данных в GPU - 2

Введение

Если вы изучали теорию вычислительных машин в 80-х или 90-х, есть вероятность, что вы упорно пытались понять, что же некоторые разработчики находят восхитительного в алгоритмах сортировки. То, что поначалу кажется незначительной задачей, оказывается краеугольным камнем Computer Science.

Но что же такое «алгоритм сортировки»? Представьте, что у вас есть список чисел. Алгоритм сортировки — это программа, получающая этот список и изменяющая порядок чисел в нём. Понятие алгоритмов сортировки часто вводится при изучении вычислительной сложности — ещё одной обширной области знания, которую я подробно рассмотрю в будущих статьях. Существует бесконечное количество способов сортировки списка элементов, и каждая стратегия обеспечивает свой собственный уникальный компромисс между затратами и скоростью.
Читать полностью »

Arrays, Collections: Алгоритмический минимум

Массивы и списки

Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники JDK 7.80.
Читать полностью »


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