Какая сортировка самая быстрая

Какой алгоритм сортировки быстрее?

Существует много видов сортировки: пузырьковая (bubble), выборкой (Selection), вставками (Insertion), куча (Heap), слиянием (Merge), быстрая (Quick). В этой статье мы постараемся определить, какой из этих алгоритмов быстрее.

Для решения поставленной задачи сгенерируем массив в Python, состоящий из пяти тысяч чисел от 0 до 1000. Потом определим время, нужное нам для завершения каждого алгоритма. И повторим каждый метод десять раз, дабы можно было точнее определить производительность.

Что получили?

Самым медленным алгоритмом оказалась пузырьковая сортировка. Возможно, она будет полезна при ознакомлении с темой алгоритмов сортировки, однако всё же Bubble Sort — не самый лучший вариант для практического применения.

А вот быстрая сортировка неплохо оправдала своё название, показав скорость, которая почти в 2 раза выше, чем при сортировке слиянием. При этом нам не потребуется дополнительное место для результирующего массива.

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

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

Наилучший способ сортировки массива.

Какой способ является самым лучшим и по вашему мнению и почему? Есть ли способы быстрее способа, основанного на алгоритме «быстрой сортировки»? Если да, то будьте добры рассказать, где можно о нем почитать.

Отслеживать
371 1 1 золотой знак 5 5 серебряных знаков 13 13 бронзовых знаков
задан 22 июн 2012 в 22:08
970 4 4 золотых знака 14 14 серебряных знаков 22 22 бронзовых знака

Лучшего метода (для всех случаев) не бывает. Если имеются какие-либо предположение относительно структуры входных данных, то можно оптимизировать процесс сортировки. Хорошая вводная статья есть на clck.ru/EiGA

24 июн 2012 в 9:58

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

• Лучшего способа нет, если говорить о «разумных» алгоритмах и не учитывать эзотерику типа Bogosort или Intelligent Design Sort.

• Стандартные операции sort в современных языках обычно используют разные алгоритмы в зависимости от размера входных данных. То есть, на маленьких размерах массивов O(N^2) сортировка вставками часто оказывается более эффективной, чем, например, O(N log N) быстрая сортировка.
• Естественно, что для больших размеров выбирается сортировка с O(N log N) временем работы.

• Можно строго доказать, что, если S — алгоритм сортировки, основанный на построении дерева решений, то O(N log N) — это минимальное возможное время работы алгоритма S в худшем его случае. А это означает, что все алгоритмы типа quicksort , mergesort , сортировки вставками и т.п. не могут работать за время, меньшее, чем O(N log N) .

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

• Из литературы — Cormen, Introduction To Algorithms.

Отслеживать
ответ дан 22 июн 2012 в 23:46
M. Williams M. Williams
23.6k 1 1 золотой знак 41 41 серебряный знак 58 58 бронзовых знаков

Кроме временной сложности желательно не забывать и требования к вспомогательной памяти. А из литературы можно вспомнить ещё третий том «Искусства программирования» Д. Кнута. Ну и ряд других книг.

23 июн 2012 в 6:32
Да, спасибо вам. Поразрядная сортировка удивила меня, ведь это уже эзотерика.
23 июн 2012 в 8:29

Надо только помнить, что за O(nlogn) стоит константа, поэтому на практике можно сортировать быстрей, чем quicksort. Для этого есть гибридные сортировки вроде Introsort или Timsort. Еще бывает не всегда важна именно верхняя крышка, иногда ориентируются на средний случай.

24 июн 2012 в 9:39

я просто оставлю это здесь

Отслеживать
ответ дан 24 июн 2012 в 17:37
12.3k 1 1 золотой знак 25 25 серебряных знаков 33 33 бронзовых знака

@Котик_хочет_кушать правильно сказал, что лучшего способа нет.

Из почти всегда применимых алгоритмов quicksort IMHO самый быстрый (время O(N*log N)), хотя (даже правильно реализованый) изредка (на практике очень редко) может привести к времени порядка O(N^2). Он требует log N дополнительной памяти, т.е. на практике можете считать, что не требует. Основной недостаток quicksort — это неустойчивый (unstable) алгоритм.

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

Из устойчивых сортировок (я рассматриваю алгоритмы со временем O(N*log N)) IMHO самым быстрым является сортировка слиянием (mergesort) в ее почти простейшей реализации, требующий N/2 дополнительной памяти.

Похожие результаты (иногда м.б. даже быстрее, но обычно медленнее) показывает timsort (это тоже разновидность сортировки слиянием). Обычно она требует 30-40% N дополнительной памяти.

Также (пользуясь случаем) хочу обратить внимание на yamsort. Еще один алгоритм и программа устойчивой (stable) сортировки слиянием c небольшой (около 6 % от размера сортируемого массива) дополнительной памятью. Он несколько медленнее timsort, но при сортировке очень больших массивов (особенно в многопользовательских системах), когда дополниетельная память вызывает paging, это алгоритм оказывается значительно быстрее других устойчивых сортировок.

По этой ссылке (в Sourse/Readme.txt) описан данный алгоритм и есть некоторые результаты измерения разных сортировок, а также исходники нескольких сортировок и пример программы для их измерения.

Radix Sort — самая быстрая сортировка для чисел и строк

Сортировки нужны для ускорения работы программ: когда у нас много данных, нам нужно как-то их организовать, чтобы по ним было легко искать и быстро обрабатывать. На небольших наборах данных это незаметно, но когда нужно работать с сотнями тысяч единиц данных, сортировка может либо ускорить работу программы, либо намертво её повесить.

Люди изобрели много сортировок для разных данных и под разные задачи. Сегодня расскажем про поразрядную сортировку — это почти как сортировка по алфавиту, но для данных. В английском языке это называется Radix sort — сортировка по основанию системы счисления.

Чтобы оценить скорость работы этого алгоритма, посмотрите видео — там собраны 24 популярных алгоритма, которые обрабатывают один массив данных. Поразрядная сортировка — вторая слева в нижнем ряду. Вы узнаете её по тому, что она закончит работу в числе первых:

Любите математику? Это для вас

Попробуйте бесплатный тренажер «Основы математики для цифровых профессий». Это все необходимые знания, чтобы закрыть пробелы в математике для айтишника.

Получите ИТ-профессию

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

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

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

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

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

Обычно реальное время работы разных алгоритмов с одинаковой сложностью на одинаковых данных может отличаться в несколько раз. Давайте вспомним, почему так получается и спросим у википедии что значит фраза «алгоритм имеет сложность O(n log n)»

Сложность алгоритма O(n log n) означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n log n, где C — некая положительная константа.

И вот этот коэффициент C и влияет на реальное время работы агоритма. Чем сложнее алгоритм, чем более продвинутые структуры данных используются в нем, тем большее количество операций необходимо выполнить при исполнении программы для поддержки всех нужных переменных и структур. То есть больше коэффициент C и реальное время работы. Конечно, еще этот коэффициент зависит от конкретной реализации, но, если уделять внимание коду, который вы пишите, и знать особенности языка разработки, основной вклад в эту константу будет вносить именно алгоритм.

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

Сравниваемые алгоритмы

Timsort

1. Специальный алгоритм разделяет входной массив на подмассивы
2. Каждый подмассив сортируется обычной сортировкой вставками
3. Отсортированные подмассивы собираются в единый массив с помощью модифицированной сортировки слиянием

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

Smoothsort

Был изобретен небезызвестным Э. В. Дейкстрой в 1981 году и является развитием идеи Heapsort — сортировки с помощью двоичной кучи (ну или пирамиды, кому как больше нравится).

1. Построить кучу, добавляя в нее по одному элементу (сложность O(log n) на каждый, всего O(n log n))
2. Извлекать максимальный элемент, который лежит в корне построенной кучи, до тех пор, пока она не станет пуста. Так как при удалении корня куча распадается на две независимых, требуется собрать их в одну за O(log n). В сумме для n элементов — также O(n log n)

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

Числа Леонардо определяются рекуррентно следующим образом:

L(0) = 1, L(1) = 1, L(i) = L(i - 2) + L(i - 1) + 1

Вот первые несколько членов этой последовательности:

1, 3, 5, 9, 15, 25, 41, .

1. Число, записанное в корне не меньше чисел в поддеревьях (потому и куча)
2. Левым поддеревом является (k-1)-я куча Леонардо
3. Правым — (k-2)-я

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

Пример структуры из куч Леонардо для 13 элементов. Используются три кучи: 4-я, 2-я и 1-я.

Для добавления элемента в такую структуру требуется перестроить некоторые из куч, чтобы сумма их размеров стала равна новому количеству элементов, а также проследить за тем, чтобы корни куч остались упорядочены по возрастанию. Такая операция имеет сложность не более O(log n).

При добавлении элемента требуется перестроить кучи (Свойство 1 куч Леонардо на картинке не восстановлено)

Извлечение же максимума похоже на добавление элемента и также имеет сложность не более O(log n).

1. Добавляя по одному, строится множество куч Леонардо для всех элементов (не более O(log n) на каждый)
2. По очереди извлекаются максимальные элементы из построенной структуры (максимумом всегда будет корень самой правой кучи) и структура восстанавливается необходимым образом (не более O(log n) на каждый элемент)

Вообще, алгоритм далеко нетривиален, а в добавок не очень понятно описан. Материалы:
Статья на википедии
Оригинальная статья — непонятная, надо долго разбираться
Оригинальная статья, откомментированная Hartwig Thomas — тоже самое, но нормальный шрифт + поясняющие комментарии. Но легче все равно не становится 🙂
Исследование алгоритма от K. Schwarz — уже понятнее, но некоторые существенные оптимизации не описаны вообще. Иллюстрации вставлены оттуда.

Shellsort (Сортировка Шелла)

Сортировка Шелла — это надстройка над сортировкой вставками; вместо одного прохода мы делаем несколько, причем на i-ом проходе мы сортируем подмассивы из элементов, стоящих друг от друга на расстоянии d_i.

При этом на последнем проходе d_i должно быть равно 1 (то есть последний шаг — это обычная сортировка вставками), это гарантирует корректность алгоритма.

Для примера: пусть необходимо отсортировать массив из 12 элементов, количество проходов равно 3, d₁ = 5, d₂ = 3, d₃ = 1
На первом шаге будут сортироваться следующие массивы:

(a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10)

(a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12)

А на третьем массив (a1. a12) целиком

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

Сложность алгоритма зависит от выбора количества проходов и значений d_i, и может сильно варьироваться; в википедии есть специальная таблица. Для тестирования я выбрал вариант, описанный здесь, в худшем случае его сложность составляет O(n 4/3 ), а в среднем O(n 7/6 ).

Если данные изначально отсортированы в нужном порядке, то не будет произведено ни одного обмена, все проходы пройдут «в холостую». Потому сложность в таком случае зависит лишь от количества проходов. Если же их количество фиксировано, то это будет просто O(n).

Требуется O(1) дополнительной памяти.

Почитать подробнее можно здесь, тут и вот тут.

Сравнение

Собственно, вот и самая интересная часть — протестировать все вышеупомянутые методы на разных данных и сравнить их реальное время работы.

• TimSort — реализация David R. Maclver, написанная для его статьи о TimSort — Хорошая, оптимизированная реализация
• SmoothSort — одна из моих реализаций, самая быстрая что мне удалось написать
  Вообще, написать этот алгоритм более-менее эффективно не очень просто. Вероятно можно написать и быстрее, и оптимальнее, но после четырех попыток я решил не продолжать 🙂
• ShellSort — реализация, написанная по мотивам примера отсюда
• Также в сравнение были добавлены обычные рекурсивные реализации quicksort и heapsort для того, чтобы можно было оценить преимущества рассматриваемых методов над традиционными

Параметры тестирования

Замерялось только время срабатывания алгоритма сортировки (в секундах), время генерации тестовых данных не учитывалось. Каждый алгоритм запускался на одних и тех же данных по три раза, брался в расчет лучший результат (чтобы кратковременные нагрузки системы не повлияли на наш честнейший эксперимент 🙂 )

Железо: ноутбук HP dv3510er, Intel Core 2 Duo 2Ггц, 2Гб RAM.
ОС: Ubuntu 11.10

Проведено четыре эксперимента на разных данных:

Эксперимент 1: Работа на обычных данных

Задачей этого экспериментая является сравнение быстродействия алгоритмов на произвольных, никак не упорядоченных данных. Было сгенерировано 10 наборов по 10 8 случайных натуральных чисел, для каждого алгоритма было замерено среднее время работы.

Сложность всех тестируемых алгоритмов в случае произвольных данных равна (кроме ShellSort) O(n log n). Собственно, здесь можно проследить влияние той самой константы C.

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

Эксперимент 2: Независимые отсортированные группы равного размера

Дано 10 8 различных натуральных чисел, отсортированных по возрастанию. Группируем их по k последовательных элементов и переставляем все группы в обратном порядке.
Пример для десяти чисел: 1 2 3 4 5 6 7 8 9 10
k = 1: 10 9 8 7 6 5 4 3 2 1
k = 3: 8 9 10 5 6 7 2 3 4 1
k = 5: 6 7 8 9 10 1 2 3 4 5
k = 10: 1 2 3 4 5 6 7 8 9 10

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

Замеры производились для всех k, равных степеням 10.

• Quicksort и Heapsort тоже любят, когда данные частично отсортированы (сравните оба графика). На асимптотическую сложность это не влияет, но скорость работы все равно возрастает в разы
• Timsort’у все равно, в каком порядке отсортированы данные, в обоих случаях он работает очень быстро
• Smoothsort имеет свое понимание частичной упорядоченности данных. Реальный прирост производительности в этом тесте заметен лишь при полностью отсортированных данных. Даже в том случае, когда массив представляет из себя небольшое количество полностью отсортированных кусков, для того чтобы переставить их местами, алгоритму требуется произвести огромное количество операций со кучами Леонардо, которые довольно «тяжелые»
• Shellsort, несмотря на большую сложность (при n = 10 8 n 7/6 > n log n), часто работает за меньшее время, чем Smoothsort. Это связано с относительной простотой алгоритма. Но при полностью отсортированных данных, Shellsort все равно вынужден сделать все проходы, пусть даже и не переставляя ни одного элемента. Поэтому при k = 10 8 результат почти самый худший из рассматриваемых алгоритмов

Эксперимент 3: Отсортированные группы разных размеров, ограниченный диапазон значений

Дано 10 8 целых чисел из ограниченного дипазона (в нашем случае [0… 100000]) и они упорядочены группами произвольного размера от 1 до k.

Такой набор данных уже как-то соответствует данным из реальных задач, мне пришлось столкнуться с таковыми для подсчета коэффициентов близости Дайса

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

Эксперимент 4: Произвольные перестановки

Сгенерируем частично упорядоченные данные другим способом: возьмем 10 8 произвольных натуральных чисел, отсортируем их и сделаем k произвольных перестановок двух элементов местами.

А этот эксперимент наконец-то позволяет Smoothsort’у «раскрыться»: становится заметным ускорение при увеличении степени отсортированности входных данных. Это связано с тем, что, в отличие от предыдущих экпериментов, здесь алгоритм «двигает» по кучам Леонардо лишь не очень большое фиксированное количество элементов, что не влечет за собой большого количества операций по перемещению элементов внутри куч. Но после определенного момента он снова становится слишком «долгим».

Итоги

Как можно было убедиться, практическая польза от описанных алгоритмов есть, со своей задачей они с переменным успехом справляются. Абсолютным лидером стал Timsort — дающий заметное ускорение при увеличении степени упорядоченности данных и работающий на уровне Quicksort в обычных случах. Не зря он признан и встроен в Python, OpenJDK и Android JDK.

Про Smoothsort в сети довольно немного информации (по сравнению с остальными алгоритмами) и не спроста: из-за сложности идеи и спорной производительности он скорее является алгоритмическим изыском, нежели применимым методом. Я нашел всего лишь одно реальное применение этого алгоритма — в библиотеке sofia-sip, предназначенной для построения IM- и VoIP-приложений.

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

Хочу заметить, что я сравнивал именно производительность, и специально не заострял внимание на других параметрах (вроде использования дополнительной памяти).

Мой субъективный вывод — если нужен очень хороший алгоритм сортировки для встраивания в библиотеку или в большой проект то лучше всего подойдет Timsort. В случае же небольших задач, где нет времени и необходимости писать сложные алгоритмы, а результат нужен быстро — то вполне можно обойтись и Quicksort’ом — так как он дает лучшую из простых в написании алгоритмов производительность.

Спасибо, что прочитали. Надеюсь, вам было интересно.

• алгоритмы сортировки
• quicksort
• heapsort
• сортировка шелла
• smoothsort
• сравнение производительности