Pull to refresh

Анимированое сравнение алгоритмов сортировки

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

(картинка Кликабельна)
Небольшое описание под катом...
Total votes 95: ↑90 and ↓5 +85
Views 9.4K
Comments 25

Наглядная демонстрация алгоритмов сортировки

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



Под катом есть еще видео
Читать дальше →
Total votes 181: ↑160 and ↓21 +139
Views 32K
Comments 46

И снова про сортировки: выбираем лучший алгоритм

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

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

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

Читать дальше →
Total votes 117: ↑114 and ↓3 +111
Views 134K
Comments 32

Сортировка слиянием без использования дополнительной памяти

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

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

Читать дальше →
Total votes 40: ↑38 and ↓2 +36
Views 35K
Comments 67

Алгоритмы сортировки. Gnome Sort на Си

Programming *C++ *Algorithms *
Sandbox
Алгоритмы сортировки. Их не много, но и не мало. Есть часто используемые, есть никому не нужные. Я решил произвести обзор этих алгоритмов, чтоб освежить и свою память, и память хабрапользователей. И начнём с редкоиспользуемого алгоритма Gnome Sort(гномья сортировка).
Читать дальше →
Total votes 36: ↑13 and ↓23 -10
Views 15K
Comments 3

Что скрывается под алгоритмом ранкинга в Apple App Store? Хабра Квест

Apps4All corporate blog Development for iOS *Algorithms *
Введение

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

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

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

Эти данные оказалось совсем не просто найти…
Читать дальше →
Total votes 56: ↑41 and ↓15 +26
Views 19K
Comments 34

На какие вопросы можно ответить, проанализировав 1 500 000 уникальных историй болезней?

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

предупреждение: под катом очень много текста
Читать дальше →
Total votes 88: ↑77 and ↓11 +66
Views 48K
Comments 14

Сортировка вставкой в хэш-таблицу

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

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

Читать дальше →
Total votes 20: ↑11 and ↓9 +2
Views 14K
Comments 19

Быстрая, экономная, устойчивая…

Algorithms *Mathematics *

Если вам понадобится алгоритм сортировки массива, который:
  • Работал бы гарантированно за 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), в которой описан алгоритм со всеми тремя свойствами.

Так что же это за алгоритм?
Total votes 155: ↑150 and ↓5 +145
Views 57K
Comments 30

Соломонова Сортировка

Algorithms *
Recovery mode
Доброго Нового Года!

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

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

Читать дальше →
Total votes 44: ↑38 and ↓6 +32
Views 29K
Comments 26

Бенчмарк 14 алгоритмов сортировки на массивах с разной размерностью и содержанием

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

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

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


Подробнее об алгоритмах
quickSort – Быстрая сортировка*
countingSort – Сортировка подсчетом*
combSort – Сортировка расчёской*
heapSort – Сортировка кучей*
mergeSort – Сортировка слиянием*
shellSort – Сортировка Шелла*
selectionSort – Сортировка выбором*
insertSort – Сортировка вставками*
gnomeSort – «Гномья» сортировка*
combinedBubbleSort – Модифицированная «Пузырьковая» сортировка
cocktailSort – «Шейкерная» сортировка*
bubbleSort – «Пузырьковая» сортировка*
oddEvenSort – Сортировка чёт-нечет
bubbleSortWithFlag – «Пузырьковая» сортировка с флагом перестановок


Читать дальше →
Total votes 36: ↑19 and ↓17 +2
Views 36K
Comments 22

Алгоритм сортировки Radix Compact. Часть 1: реализация на CPU

C++ *Algorithms *
Sandbox
В одном из моих проектов, который был связан с компьютерным зрением, возникла задача сортировки большого массива чисел (около 100 млн. элементов). Код сортировки должен был выполняться как можно быстрее, причем с возможностью исполнения на нескольких процессорах, и желательно на GPU. Сортировка реализованная в стандартной библиотеке C++ не подходила: она основана на алгоритме Quick Sort, который на данный момент не поддается массивному распараллеливанию на GPU. Поиск других способов привел к алгоритму Radix Sort, но в найденных источниках описывалась реализация требующая большого расхода памяти, точнее памяти требовалось: (количество элементов массива) * (размер radix массива). Для массива 100 млн. элементов и radix массиве размером 256 элементов памяти потребовалось бы 25.6 Гб, мало реальное требование, на текущий момент развития вычислительной техники. Но для распараллеливания вычислений алгоритм Radix Sort подходит неплохо, собственно поэтому автор попытался доработать этот способ, чтобы уменьшить расход памяти до приемлемых значений.
Читать дальше →
Total votes 23: ↑18 and ↓5 +13
Views 21K
Comments 23

Четно-нечетная сортировка слиянием Бэтчера

Programming *Algorithms *
Sandbox

Введение


Алгоритм четно-нечетной сортировки слиянием (odd-even mergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Лично я узнал о нем когда разбирался с MPI и увидел тестовое задание на coursera: написать сортировку Бэтчера.
Читать дальше →
Total votes 15: ↑12 and ↓3 +9
Views 23K
Comments 4

Поразрядная сортировка с человеческим лицом

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

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

Возможно, именно поэтому многие люди до сих пор считают поразрядку алгоритмом, представляющим исключительно академический интерес, и малоприменимым в реальности. Однако, это заблуждение.
Читать дальше →
Total votes 28: ↑26 and ↓2 +24
Views 34K
Comments 6

Еще один разбор пузырьковой сортировки

Programming *Java *Algorithms *
Recovery mode
Tutorial

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

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

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

Читать дальше →
Total votes 13: ↑7 and ↓6 +1
Views 13K
Comments 12

Метод сортировки FlashSort

Open source *Algorithms *C *Mathematics *
Привет всем!

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

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

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

Так вот, мне всегда было интересно, почему уделяется так мало внимания методам сортировки без сравнения (поразрядная, блочная и т.п.). Ведь подобные методы относятся к классу быстрых алгоритмов, выполняются за О(N) количество чтений и перестановок и при удачно подобранных данных могут выполняться за линейное время.
Читать дальше →
Total votes 29: ↑27 and ↓2 +25
Views 24K
Comments 26

Сортировка огромного файла с массивом при известном словаре данных

Programming *Algorithms *
Recovery mode
Sandbox
Привет Хабр! Недавно пришло интересное задание:
Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.

Самым ленивым способом отсортировать можно используя «внешнюю сортировку со слиянием», но это весьма тяжёлый и долгий метод. В этой публикации я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.
Читать дальше →
Total votes 29: ↑17 and ↓12 +5
Views 12K
Comments 30

Анализ использования избыточности данных в качестве требуемой дополнительной памяти при сортировке алгоритмом слияния

C++ *Algorithms *
Sandbox

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


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

image

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

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

1. Сортировка слиянием;
2. Сортировка слиянием без использования буфера;
3. Естественная сортировка слиянием;
4. Естественная сортировка слиянием без использования буфера;
5. Модифицированная естественная сортировка слиянием;
6. Модифицированная естественная сортировка слиянием без использования буфера;
7. std::sort.
Читать дальше →
Total votes 25: ↑24 and ↓1 +23
Views 6.3K
Comments 3

Пузырьковая сортировка и бинарный поиск на PHP (обучение, эксперименты)

PHP *Delirium coding Algorithms *

Введение


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

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

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

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


Читать дальше →
Total votes 27: ↑14 and ↓13 +1
Views 13K
Comments 17

Описание алгоритмов сортировки и сравнение их производительности

C++ *Algorithms *
Sandbox

Вступление


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

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать дальше →
Total votes 80: ↑76 and ↓4 +72
Views 475K
Comments 55
1