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

(картинка Кликабельна)

Трансильванский университет Sapientia представил свой новый обучающий курс по алгоритмам сортировки. Стоит отметить талант создателей и высокую наглядность пособия.



Под катом есть еще видео

Недавно на хабре в очередной подняли тему алгоритмов сортировки, а именно был хорошо описан метод Timsort.

Он, имея сложность не более O(n log n), ускоряется в случае сортировки частично упорядоченных данных и имеет сложность O(n), если данные изначально отсортированны. Но это не единственный алгоритм с такими заявленными свойствами. Существует еще как минимум два более-менее известных метода с похожей сложностью — это Smoothsort и сортировка Шелла.

Но то, что они имеют похожую сложность, совсем не значит, что все они работают одинаково быстро. Я попытался сравнить их реальную скорость работы на разных данных и посмотреть кто лучше справляется со своей задачей.

Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.

Но я все-таки решил попробовать.

Алгоритмы сортировки. Их не много, но и не мало. Есть часто используемые, есть никому не нужные. Я решил произвести обзор этих алгоритмов, чтоб освежить и свою память, и память хабрапользователей. И начнём с редкоиспользуемого алгоритма Gnome Sort(гномья сортировка).

Введение

Когда в разговорах между людьми речь заходит о мобильных приложениях, часто приходиться слышать об астрономических суммах, которые зарабатывают те или иные всемирно известные разработчики или об огромном числе загрузок того или иного приложения. СМИ то и дело сообщают о запуске на МКС плюшевых свиней из Angry Birds, а в США и вовсе Цукерберг купил Instagram за 1 000 000 000 долларов.

Многие люди любят говорить о мобильных приложениях. Это современная, интересная, наконец, модная тема и действительно заслуживает внимания.

Вскоре после того, как мы начали делать проект Apps4All летом 2011 года, я стал интересоваться вопросом, сколько раз скачали или сколько зарабатывает то или иное приложение. Общаясь с другими разработчиками и представителями венчурных фондов и корпораций, я также обратил внимание, что они часто интересуются данными об успехах мобильных приложений.

Эти данные оказалось совсем не просто найти…

Существует ли связь между астмой и шизофренией?
Диабет и биполярное расстройство личности — могут ли они иметь что-то общее?
Сможет ли выявить столь нетривиальные связи анализ базы данных по 1500000 пациентов США?

_{предупреждение: под катом очень много текста}

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

Кому интересно – прошу под кат.

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

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

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

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

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

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

Пусть имеется набор 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

В этой статье речь пойдёт о бенчмарке алгоритмов сортировки, написанном на PHP.

Всего представлено 14 алгоритмов:

• quickSort
• countingSort
• combSort
• heapSort
• mergeSort
• shellSort
• selectionSort
• insertSort
• gnomeSort
• combinedBubbleSort
• cocktailSort
• bubbleSort
• oddEvenSort
• bubbleSortWithFlag

В одном из моих проектов, который был связан с компьютерным зрением, возникла задача сортировки большого массива чисел (около 100 млн. элементов). Код сортировки должен был выполняться как можно быстрее, причем с возможностью исполнения на нескольких процессорах, и желательно на GPU. Сортировка реализованная в стандартной библиотеке C++ не подходила: она основана на алгоритме Quick Sort, который на данный момент не поддается массивному распараллеливанию на GPU. Поиск других способов привел к алгоритму Radix Sort, но в найденных источниках описывалась реализация требующая большого расхода памяти, точнее памяти требовалось: (количество элементов массива) * (размер radix массива). Для массива 100 млн. элементов и radix массиве размером 256 элементов памяти потребовалось бы 25.6 Гб, мало реальное требование, на текущий момент развития вычислительной техники. Но для распараллеливания вычислений алгоритм Radix Sort подходит неплохо, собственно поэтому автор попытался доработать этот способ, чтобы уменьшить расход памяти до приемлемых значений.

Введение

Алгоритм четно-нечетной сортировки слиянием (odd-even mergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Лично я узнал о нем когда разбирался с MPI и увидел тестовое задание на coursera: написать сортировку Бэтчера.

Несмотря на известность алгоритма поразрядной сортировки, в интернете сложно найти приличную его реализацию на языке C++ (честно говоря, думаю, что и на других языках тоже). Почти всё, что находится поисковиками, чудовищно либо в плане кода, либо в плане эффективности. А чаще всего плохо и то, и другое.

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

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

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

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

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

Привет всем!

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

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


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

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

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

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

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

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

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



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

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

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

Введение

Хотел бы поделиться с сообществом своей реализацией пузырьковой сортировки и бинарного поиска. Проект сделал исключительно в учебных целях.

Когда меня раньше спрашивали на собеседовании об алгоритмах сортировки и реализации поиска по массивам данных — я терялся и считал, что для реализации подобных вещей надо быть как минимум талантливым отличником-олимпиадником, что это сложно-долго-малоизучено и т.п. :) Так же я находил курсы, где за несколько недель (месяцев) предлагают научить всех желающих всему-всему по алгоритмам, сортировкам, криптографии. Но ведь сейчас есть Интернет, а в нем уже все выложено и известно? Остается только поднять и изучить нужные знания и практически реализовать и закрепить приобретенные знания.

Итак, приступим к реализации самих алгоритмов. Забегая вперед скажу, что статья состоит из трех логических частей: реализация алгоритмов, тестирование написанного кода (PHPUnit) и проведение нагрузочных тестов (базовые функции языка VS написанный код).

Т.е. как бы имитируется разработка некой системы (выполнение практической задачи) и прохождение по всем обязательным этапам (исходя из существующих на сейчас «стандартов» разработки).

Вступление

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

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