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

в 13:54, , рубрики: c++, timsort, Алгоритмы, алгоритмы сортировки, битонная сортировка, блочная сортировка, быстрая сортировка, гномья сортировка, пирамидальная сортировка, поразрядная сортировка, сортировка вставками, сортировка выбором, сортировка деревом, сортировка пузырьком, сортировка расчёской, сортировка слиянием, сортировка шелла, тестирование производительности, шейкерная сортировка

Вступление

На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать полностью »

в 13:49, , рубрики: javascript, Алгоритмы, алгоритмы сортировки, визуализация, визуализация данных

Доброго времени суток всем читателям и авторам habrahabr.ru. Речь в данной статье будет идти о визуализации простейших алгоритмов сортировки.

Визуализация алгоритмов сортировки обменом на JavaScript - 1

На выполнение данной работы меня вдохновил Timo Bingmann – аспирант из Института теоретической информатики и алгоритмов при Технологическом институте Карлсруэ (Германия) [1]. Тимом была написана отличная статья, где можно почитать немного о истории визуализаций и аудификаций алгоритмов [2]. Программисты, как никто знают, как тяжело идет процесс понимания абстрактных сущностей, и как сильно в этом помогают метафоры и методы визуализации. Когда какому-либо объекту из реальной жизни аналогично присваиваются свойства и методы виртуальных объектов.

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

в 12:39, , рубрики: benchmark, c++, merge sort, sorting, Алгоритмы, алгоритмы сортировки, бенчмарки, сортировка слиянием

Алгоритмы сортировки

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

image

Данный анализ я проводил в качестве летней практики в компании «Программные технологии».
Сортируемая последовательность не имеет заголовка, числа в ней имеют различную разрядность и хранятся без выравнивания. Между числами стоят разделители (0xFF).

Для осуществления сортировки с помощью библиотечной функции вводится дополнительный уровень данных – контейнер, содержащий указатели на области памяти, каждая из которых содержит одно BCD число. В сравнении участвуют:

1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.

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

в 5:41, , рубрики: Алгоритмы, алгоритмы сортировки, большие объемы данных, Программирование, сортировка

Привет! Недавно пришло интересное задание:

Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.

Самым ленивым способом отсортировать можно используя «внешнюю сортировку со слиянием», но это весьма тяжёлый и долгий метод. В этой публикации я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.
Читать полностью »

в 10:55, , рубрики: C, open source, Алгоритмы, алгоритмы сортировки, математика, оптимизация

Привет всем!

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

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

Сортировка пузырьком
Вот, к примеру, подобной реализации метода сортировки “пузырьком” меня учили в одной крупной IT-компании. Этот метод использовался матёрыми программистами там повсеместно.

Так вот, мне всегда было интересно, почему уделяется так мало внимания методам сортировки без сравнения (поразрядная, блочная и т.п.). Ведь подобные методы относятся к классу быстрых алгоритмов, выполняются за О(N) количество перестановок и при удачно подобранных данных могут выполняться за линейное время.Читать полностью »

в 0:25, , рубрики: java, Алгоритмы, алгоритмы сортировки, новичкам, Программирование
Еще один разбор пузырьковой сортировки - 1

Однажды, новогодним вечером, вдохновившись статьей про пузырьковую сортировку и ее модификации, я решил написать свою реализацию, и подумать, как бы я смог ее улучшить. А заодно начать все-таки изучать JAVA (по профессии я не программист, хотя немного писал).

Зачем в наши дни нужна сортировка пузырьком?
Она ведь практически самая медленная.
У нее самый высокий (квадратичный) алгоритм сложности.

Но! Она самая простая в реализации и весьма наглядная, и часто используется в образовательных целях или на собеседованиях джуниоров/интернов.
Кроме того, с небольшими модификациями, можно достичь интересных результатов.
Новичков в программировании и заинтересовавшихся — прошу под кат.

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

в 10:09, , рубрики: Алгоритмы, алгоритмы сортировки, метки:

Доброго Нового Года!

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

Пусть имеется набор N из n целых положительных чисел от 1 до n.
Самоочевидно, что для хранения n чисел необходимо иметь n ячеек. Вне зависимости от порядка, в котором числа будут записаны.

Исходный массив

3 5 2 1 8 4 7 6 9 10

Несложно представить, что неупорядоченный набор N достаточно просто заменить упорядоченным (по возрастанию, или по убыванию), записав упорядоченный набор на место неупорядоченного.

Упорядоченный массив

1 2 3 4 5 6 7 8 9 10

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

в 3:01, , рубрики: Алгоритмы, алгоритмы сортировки, математика, сортировка, сортировка слиянием, метки: , ,

Быстрая, экономная, устойчивая…
Если вам понадобится алгоритм сортировки массива, который:

  • Работал бы гарантированно за O(N*log(N)) операций (обменов и сравнений);
  • Требовал бы O(1) дополнительной памяти;
  • Был бы устойчивым (то есть, не менял порядок элементов с одинаковыми ключами)

то вам, скорее всего, предложат ограничиться любыми двумя из этих трёх пунктов. И, в зависимости от вашего выбора, вы получите, например, либо сортировку слиянием (требует O(N) дополнительной памяти), либо пирамидальную сортировку (неустойчив), либо сортировку пузырьком (работает за O(N2)). Если вы ослабите требование на память до O(log(N)) («на рекурсию»), то для вас найдётся алгоритм со сложностью O(N*(log(N)2) — довольно малоизвестный, хотя именно его версия используется в реализации метода std::stable_sort().

На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N)2) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан именно такой алгоритм.

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

в 9:47, , рубрики: алгоритмы поиска, алгоритмы сортировки, аутизм, биоинформатика, будущее здесь, Поисковые машины и технологии, метки: , , ,

Существует ли связь между астмой и шизофренией?
Диабет и биполярное расстройство личности — могут ли они иметь что-то общее?
Сможет ли выявить столь нетривиальные связи анализ базы данных по 1500000 пациентов США?
На какие вопросы можно ответить, проанализировав 1 500 000 уникальных историй болезней?
предупреждение: под катом очень много текста
Читать полностью »

в 8:22, , рубрики: Алгоритмы, алгоритмы сортировки, метки:

Pigeonhole сортировка — это такой старый способ несравнивающей сортировки, в котором элементы входного массива «разбрасываются» по массивам, соответствующим домену индекса сортировки, а потом собираются вместе в нужном порядке.

Например, у нас есть какой-то немаленький массив процессов с их приоритетами. Нам надо сформировать из этого правильную очередь. Пусть домен типа приоритета будет состоять из трех значений: высокий, средний, низкий.

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

Это абсолютно прозрачно и здорово, но работает все хуже и хуже с тем, как растет мощность домена. Кроме одного случая.
Читать полностью »

123
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js