Три дня назад я задумался об объединении сортировки подсчётом и деревом. Обсудив её с коллегой, пришли к следующему решению: вместо TreeSet использовать HashMap (при чём здесь вообще TreeSet, можно посмотреть ниже). Но и этого мне показалось мало, так что я решил реализовать собственную хэш-таблицу и посмотреть, что из этого выйдет. Результаты показались мне довольно интересными интересными.
Читать полностью »
Рубрика «алгоритмы сортировки» - 2
Сортировка… хэш-таблицей (ещё подсчётом-деревом и HashMap’ом)
2018-07-26 в 15:53, admin, рубрики: Алгоритмы, алгоритмы сортировки, математикаСортировки вставками
2018-07-02 в 11:57, admin, рубрики: java, python, Алгоритмы, алгоритмы сортировки, визуализация данных, Программирование
Общая суть сортировок вставками такова:
- Перебираются элементы в неотсортированной части массива.
- Каждый элемент вставляется в отсортированную часть массива на то место, где он должен находиться.
Сравнение сортировок обменами
2018-06-29 в 12:02, admin, рубрики: php, python, Алгоритмы, алгоритмы сортировки, Программирование, Тестирование IT-систем
Сферические алгоритмы в вакууме — это прекрасно. Однако давайте спустимся с небес на грешную землю и посмотрим как вся эта теоретическая красота покажет себя на практике.
Читать полностью »
Сортировки обменами
2018-06-20 в 8:22, admin, рубрики: python, Алгоритмы, алгоритмы сортировки, визуализация данных, ненормальное программирование, Совершенный код
Если описать в паре предложений по какому принципу работают сортировки обменами, то:
- Попарно сравниваются элементы массива
- Если элемент слева* больше элемента справа, то элементы меняются местами
- Повторяем пункты 1-2 до тех пор, пока массив не отсортируется
* — под элементом слева подразумевается тот элемент из сравниваемой пары, который находится ближе к левому краю массива. Соответственно, элемент справа находится ближе к правому краю.
Читать полностью »
Параллельная сортировка данных в GPU
2018-01-03 в 7:08, admin, рубрики: Алгоритмы, алгоритмы сортировки, математика, шейдеры
В этой статье я познакомлю вас с концепцией параллельной сортировки. Мы обсудим теорию и реализацию шейдера, сортирующего пиксели.
GIF
Введение
Если вы изучали теорию вычислительных машин в 80-х или 90-х, есть вероятность, что вы упорно пытались понять, что же некоторые разработчики находят восхитительного в алгоритмах сортировки. То, что поначалу кажется незначительной задачей, оказывается краеугольным камнем Computer Science.
Но что же такое «алгоритм сортировки»? Представьте, что у вас есть список чисел. Алгоритм сортировки — это программа, получающая этот список и изменяющая порядок чисел в нём. Понятие алгоритмов сортировки часто вводится при изучении вычислительной сложности — ещё одной обширной области знания, которую я подробно рассмотрю в будущих статьях. Существует бесконечное количество способов сортировки списка элементов, и каждая стратегия обеспечивает свой собственный уникальный компромисс между затратами и скоростью.
Читать полностью »
Arrays, Collections: Алгоритмический минимум
2017-12-09 в 12:18, admin, рубрики: java, java core, Алгоритмы, алгоритмы поиска, алгоритмы сортировкиArrays, Collections: Алгоритмический минимум
Массивы и списки
Недавно на собеседовании в крупную компанию на должность Java разработчика меня попросили реализовать стандартный алгоритм сортировки. Поскольку я никогда не реализовывал самописные алгоритмы сортировки, а пользовался всегда готовыми решениями, у меня возникли затруднения с реализацией. После собеседования я решил разобраться в вопросе и подготовить список основных алгоритмов сортировки и поиска, которые используются в стандартном пакете java — Java Collections Framework (JCF). Для этого я изучил исходники JDK 7.80.
Читать полностью »
Описание алгоритмов сортировки и сравнение их производительности
2017-08-18 в 13:54, admin, рубрики: c++, timsort, Алгоритмы, алгоритмы сортировки, битонная сортировка, блочная сортировка, быстрая сортировка, гномья сортировка, пирамидальная сортировка, поразрядная сортировка, сортировка вставками, сортировка выбором, сортировка деревом, сортировка пузырьком, сортировка расчёской, сортировка слиянием, сортировка шелла, тестирование производительности, шейкерная сортировкаВступление
На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.
Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать полностью »
Визуализация алгоритмов сортировки обменом на JavaScript
2017-02-26 в 13:49, admin, рубрики: javascript, Алгоритмы, алгоритмы сортировки, визуализация, визуализация данныхДоброго времени суток всем читателям и авторам habrahabr.ru. Речь в данной статье будет идти о визуализации простейших алгоритмов сортировки.
На выполнение данной работы меня вдохновил Timo Bingmann – аспирант из Института теоретической информатики и алгоритмов при Технологическом институте Карлсруэ (Германия) [1]. Тимом была написана отличная статья, где можно почитать немного о истории визуализаций и аудификаций алгоритмов [2]. Программисты, как никто знают, как тяжело идет процесс понимания абстрактных сущностей, и как сильно в этом помогают метафоры и методы визуализации. Когда какому-либо объекту из реальной жизни аналогично присваиваются свойства и методы виртуальных объектов.
Анализ использования избыточности данных в качестве требуемой дополнительной памяти при сортировке алгоритмом слияния
2016-09-27 в 12:39, admin, рубрики: benchmark, c++, merge sort, sorting, Алгоритмы, алгоритмы сортировки, бенчмарки, сортировка слияниемАлгоритмы сортировки
В этой статье речь пойдет о сравнении некоторых алгоритмов сортировки, реализованных на C++ для последовательности не упакованных BCD чисел большого размера.
Данный анализ я проводил в качестве летней практики в компании «Программные технологии».
Сортируемая последовательность не имеет заголовка, числа в ней имеют различную разрядность и хранятся без выравнивания. Между числами стоят разделители (0xFF).
Для осуществления сортировки с помощью библиотечной функции вводится дополнительный уровень данных – контейнер, содержащий указатели на области памяти, каждая из которых содержит одно BCD число. В сравнении участвуют:
1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.