Сортировка больших массивов случайных чисел (C++)

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

Технические подробности проведения тестов
Код программы-оболочки, замеряющей скорость сортировки (С++)

 

Содержание

Рассматриваемые сортировки:

  1. Пузырьковая (Bubble)
  2. Двунаправленная (Bidirectional)
  3. Чёт-нечет (Odd-even)
  4. Выбором (Selection)
  5. Вставками (Insertion)

  6. Пирамидная (Heap)
  7. Слиянием (Merge)
  8. Шелла (Shell)
  9. Расчёской (Comb)
  10. Быстрая (Quick)

(Первые пять видов сортировки можно условно назвать 'простыми', последние пять 'быстрыми')

Суммирующие графики
Замечания и внешние ссылки

Чтобы увидеть графики в более крупном масштабе, щёлкните на них.

 


Часть А. Простые виды сортировок.

Пузырьковая сортировка
(Bubble sort)

Wiki (ru) / Wiki (eng)
Статья на kvodo.ru
Статья на sorting.valemak.com
Считается учебной. На практике может использоваться лишь для сортировки маленьких массивов. И в этом случае лучше взять классическую сортировку, а не её модификацию.

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

Временная сложность (определение термина). Для среднего и худшего случая O (n2), для лучшего O (n)

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

Устойчив. (Устойчивость показывает, могут ли сущности, сортируемые по одному из своих параметров, в случае его равного значения меняться местами. См. объяснение на примере тортов. Устойчивость алгоритма обеспечивает больше порядка в системе.)

Пузырьковая сортировка (Bubble sort)

 

Модифицированная пузырьковая сортировка

 

 

 

Двунаправленная сортировка = Шейкерская = Перемешиванием
(Bidirectional bubble sort = Cocktail shaker sort = Ripple sort = Shuffle sort = Shuttle sort)

Wiki (ru) / Wiki (eng)
Статья на kvodo.ru
Статья на sorting.valemak.com
Статья на studfiles.net
Алгоритм является лидером по количеству названий, которые имеет.

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

Временная сложность. Аналогично пузырьковой для среднего и худшего случая O (n2), для лучшего O (n)

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

Устойчив.

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

Двунаправленная сортирова = Сортировка перемешиванием = Шейкерная
(Bidirectional bubble sort = Cocktail shaker sort = ripple sort = shuffle sort = shuttle sort)

 

Двунаправленная сортировка - модификация

 

 

Сортировка чёт-нечет
(Odd-even sort = Brick sort)

Wiki (ru) / Wiki (eng)
Статья на sorting.valemak.com
Статья на studfiles.net
Является модификацией пузырьковой сортировки, разработана для использования на параллельных процессорах. Но если у нас нет соответствующего инструмента управления распределением нагрузки, то получающаяся скорость лишь немного выше пузырьковой, заметно проигрывая сортировке выбором.

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

Временная сложность. Аналогично пузырьковой для среднего и худшего случая O (n2), для лучшего O (n)

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

Устойчив.

Сравнение основных 5 медленных алгоритмов сортировки

Сортировка чёт-нечет (Odd–even sort)

 


 

Сортировка выбором
(Selection sort)

Wiki (ru) / Wiki (eng)
Статья на sorting.valemak.com
Статья на studfiles.net

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

Временная сложность. O (n2) на всех случаях.

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

Неустойчив.

Сортировка выбором (Selection sort) - с внутренним объявлением переменных

 

Сортировка выбором (Selection sort) - с внешним объявлением переменных

 

 

Сортировка вставками
(Insertion sort)

Wiki (ru) / Wiki (eng)
Статья на sorting.valemak.com
Статья на studfiles.net
Сортировка вставками является наиболее быстрым из простых способов, так что рекомендую уделить ей больше внимания, чем ранее рассмотренным.

Суть. Цикл последовательно проходит по всем элементам, начиная со второго по счёту, постепенно выстраивая упорядоченный подмассив. (Со второго - поскольку подмассив, состоящий из одного элемента, уже является упорядоченным.) Текущий элемент вставляется в подходящее для него место среди ранее упорядоченных элементов, сдвигая более крупные вправо.

Временная сложность. Аналогично пузырьковой для среднего и худшего случая O (n2), для лучшего O (n)

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

Устойчив.

Сортировка вставками (Insertion sort) - с внутренним объявлением переменных

 

Сортировка вставками (Insertion sort) - с внешним объявлением переменных

 

Сортировка вставками (Insertion sort) - плохие модификации

 

 

 

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



Общее сравнение алгоритмов простых сортировок

 

 


Часть Б. Быстрые виды сортировок.
 

Пирамидная сортировка = Сортировка кучей
(Heapsort)

Wiki (ru) / Wiki (eng)
Статья на iproc.ru
Статья на sorting.valemak.com

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

Временная сложность. O (n * log n) на всех случаях. В том числе отсутствует деградация на неудачных случаях, которая является больным местом быстрой сортировки.

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

Неустойчив.

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

Из-за сложности реализации выигрыш получается только на больших размерах массива (от нескольких тысяч элементов). На более мелких массивах обычно рекомендуют применять сортировку Шелла. Алгоритм известен тем, что активно применяется в ядре Linux.

Пирамидная сортировка = сортировка кучей (Heapsort)

Примечание: операции *2 и /2 в вышеприведённом алгоритме можно заменить на операции бинарного сдвига <<1 и >>1. Однако при замерах сколь либо заметного влияния на производительность от этого обнаружено не было. Современные компиляторы C++ достаточно умны, чтобы самим выполнить такие оптимизирующие подстановки.

 

Сортировка слиянием
(Merge sort)

Wiki (ru) / Wiki (eng)
Статья на kvodo.ru
Статья на sorting.valemak.com

Суть. Исходный массив делится надвое на всё меньшие подмассивы, пока количество элементов в очередных не станет равным 2 или 1. Если в подмассиве 2 элемента, то он упорядочивается банальным сравнением. А подмассив из одного элемента по своей сути является упорядоченным. Затем происходит обратный процесс - слияние подмассивов. Поскольку подмассивы к этому времени являются упорядоченными, то можем сравнивать лишь элементы, стоящие в их начале. И отслеживаем, чтобы подмассив не иссяк.

Временная сложность. Аналогично пирамидной сортировке O (n * log n) на всех случаях. В том числе отсутствует деградация на неудачных случаях, которая является больным местом быстрой сортировки.

Расход памяти. n (Требует дополнительной памяти, примерно равной размеру исходного массива. Память расходуется на рекурсивный вызов и на постоянное создание вспомогательных подмассивов). В этом большой недостаток данного алгоритма по сравнению с пирамидным.

Устойчив.

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

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

Сортировка слиянием (Merge sort) - вариант 1

 

Сортировка слиянием (Merge sort) - вариант 2 - самый быстрый из рассмотренных

В первом варианте в рекурсивную функцию передаётся ссылка на начало оригинального массива, плюс левая и правая граница диапазона, который следует обработать.
В втором (модифицированном) варианте рекурсивной функции передаются указатели на границы подмассива. Как показывают замеры, это увеличивает быстродействие алгоритма на ~3%.

 

Сортировка слиянием (Merge sort) - вариант 3

 

Сортировка слиянием (Merge sort) - вариант 4

Разница между 3-им и 4-ым вариантами такая же, как между двумя первыми. Вновь передача по ссылке оказалась немного эффективнее.

 

 

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

Wiki (ru) / Wiki (eng)
Статья на sorting.valemak.com
Статья на algolist.manual.ru
Статья на studfiles.net
Статья на hbfs.wordpress.com (eng)
Статья на rosettacode.org (eng)
Статья на interactivepython.org (eng)
Существенно улучшенная модификация сортировки вставками (Insertion sort). Получается из неё таким же образом, как сортировка расчёской из пузырьковой.

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

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

Временная сложность. Сильно зависит от закона изменения длины промежутка.

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

Нестабильна.

Существует множество модификаций правила уменьшения последовательности промежутков. Список можно посмотреть в англоязычной Wiki. Существует множество улучшений первоначального правила, выдвинутого Шеллом. Широко известен вариант Седжвика (Sedgewick) для чётного и нечётного случаев, созданный в 1986 году, но он сложен в реализации, и при этом проигрывает более поздним модификациям.

Самым совершенным считается ряд, составленный Циурой (Ciura) в 2001 году. Создан эмпирическим путём (на основании экспериментальных данных) и позволяет обрабатывать массивы размером до нескольких тысяч элементов. Из математически герерируемых последовательностей самая последняя предложена Токудой (Tokuda) в 1992.

 
Сортировка Шелла (Shellsort) - gap sequence of Shell (1959)

 

Сортировка Шелла (Shellsort) - gap sequence of Tokuda (1992)

 

Сортировка Шелла (Shellsort) - gap sequence of Ciura (2001)

 

 

Сортировка расчёской
(Comb sort)

Wiki (ru) / Wiki (eng)
Статья на sorting.valemak.com
Статья на studfiles.net
Существенно улучшенная модификация пузырьковой сортировки.

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

Временная сложность. Для худшего случая O (n2), для лучшего O (n * log n). Для среднего случая не совсем понятно. Стоит ориентироваться на O (n2  / 2p), хотя в некоторых местах упоминают O (n * log n) , а где-то  O (n2). Нижеприведённые замеры, сделанные как раз для среднего случая, показали высокую эффективность алгоритма.

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

Нестабильна.

Сортировка расчёской (Comb sort) - вариант 1

 

Сортировка расчёской (Comb sort) - вариант 2

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

 

Быстрая сортировка
(Quick sort)

Wiki (ru) / Wiki (eng)
Статья на kvodo.ru
Статья на sorting.valemak.com
Статья на studfiles.net
Существенно улучшенная модификация пузырьковой сортировки.  Любопытный факт: усовершенствование самого неэффективного метода в результате дало один из самых эффективных.

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

Временная сложность. В лучшего и общем случаев O (n * log n). Существуют разновидности алгоритма, которые для лучшего случая дают n. На специально подобранных неудачных наборах может взлететь до O (n2).

Расход памяти. В общем случае log n. На неудачных подборках n. (Элементы лишь переставляются, так что расхода памяти на создание дополнительных массивов нет.  Но она теряется на рекурсию, а именно на хранение адресов возврата и локальных переменных.)

Неустойчив. Существуют стабильные модификации.

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

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

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

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

 

График, демонстрирующий эффективность сортировки Ломуто по сравнению с другими логарифмами

 

Быстрая сортировка, разбиение Ломуто (QuickSort, Lomuto partition scheme)

 

Быстрая сортировка, разбиение Ломуто (QuickSort, Lomuto partition scheme) -mod

Переменная prt является разделителем массива и введена в алгоритм для наглядности. В случае разбиения Хоара избавление от неё ускоряет работу алгоритма на ~3%. Однако в случае разбиения Ломуто почему-то наблюдается прямо обратная ситуация - перепроверено, во время эксперимента функции местами спутаны не были. Объяснить не могу, возможно, существуют какие-то нюансы работы компилятора или процессора.

Быстрая сортировка, разбиение Хоара (QuickSort, Hoare partition scheme)

 

Быстрая сортировка, разбиение Хоара (QuickSort, Hoare partition scheme) -mod

Второй вариант разбиения Хоара чуть эффективнее, однако разница символична.

Примечание 1. С целью увеличения эффективности алгоритма мною была сделана попытка определить функцию Partition как встроенную (перед ней было прописано inline). Однако на замерах изменения скорости алгоритма от этого замечено не было. Компилятор и сам до этого додумался.
Примечание 2. Другая попытка усовершенствования: перенос содержимого функции Partition внутрь QuickSort. Но и здесь заметного изменения скорости не зафиксировалось. Возможно, небольшая выгода имеется, но в случае массива из миллиона элементов она прячется в погрешностях.

 

Быстрая сортировка, разбиение Хоара (QuickSort, Hoare partition scheme) -mod, optimized

 

 

 

Суммирующие графики

Суммирующая таблица с результатами измерения по основным алгоритмам. Точнее, её сокращённый вариант, где показан каждый второй результат. Графики построены на основе полного набора данных.

1 000 - 16 000 элементов * 0.01 сек (на быстрых методах сортировки имеем большие погрешности):
Суммирующий график основных видов сортировки (<=65536000 элементов)

1 000 - 32 000 элементов * 0.005 сек
Суммирующий график основных видов сортировки (1000-32000 элементов)

≤ 65 536 000 элементов * 10 сек:
Суммирующий график основных видов сортировки (<=65536000 элементов)

≤ 65 536 000 элементов * 10 сек, логарифмический
Суммирующий график основных видов сортировки (<=65536000 элементов, логарифмический)

 

 

Замечания и внешние ссылки

Общее замечание 1.
Иногда можно встретить мнение, что в C++ цикл for(;;++i) работает быстрее, чем цикл for(;;i++). Практическое измерение времени выполнения 30 циклов каждого вида показало, что никакой разницы нет. Использование в приведённых выше алгоритмах записи ++i обосновано лишь привычкой автора, не более.

Общее замечание 2.
Наблюдения (не только на основании этого теста, но и другие) показывают, что при определении чётности-нечётности числа бинарная операция i&1 выполняется немного быстрее, чем традиционно-математеческая i%2 . Но это исключение, и возможно, даже оно обосновано неучётом какого-то фактора. Другие тесты показывают, что нет никакой разницы в производительности между операциями *2 и /2 с одной стороны и бинарными сдвигами <<1 и >>1 с другой. Современные компиляторы C++ отлично справляются с задачами подобной микрооптимизации кода. И даже если бинарная i&1 действительно выполняется быстрее i%2 , то в ближайшие пару лет и это место отшлифуют. Пишите код так, как читабельнее.

Общее замечание 3.
В некоторых циклах происходят рассчёты с использованием вспомогательной  переменной, которая за пределами цикла не используется. Иногда возникает вопрос, лучше объявить её внутри цикла или снаружи его. Одни измерения (не только представленные здесь, но и другие) показывают, что объявлять переменную внутри цикла, как ни странно это может вначале показаться, немного выгоднее. Другие тесты показывают, что никакой разницы нет. Чуть более быструю работу циклов с внутренним объявлением переменных можно объяснить тем, что процессору при её обработке достаточно своих собственных регистров: сам создал, сам уничтожил - не нужно обращаться к далёкой оперативке (для верности можно дополнительно объявить переменную как register). В любом случае, при работе с современными компиляторами C++ не нужно опасаться объявлять переменные внутри цикла. Как минимум, это не повредит, зато сделает некоторые места более понятными.

 

 


Другие хорошие места, где можно почитать о сортировках:
Simple comparison of sorting algorithms in C++ (codereview.stackexchange.com) - приведён график сравнения 5 основных алгоритмов сортировок. Однако исследование сделано с наскока: проанализированная там merge-sort реализована через разбиение Ломуто, а не через более эффективное разбиение Хоара. А heap-sort перемудрена и недодумана - её также можно было сделать более эффективной.
Time Comparison of Quick Sort, Insertion Sort and Bubble Sort (vinayakgarg.wordpress.com) - приведён график сравнения 3 упомянутых в названии типов сортировки.
Sorting Algorithms (betterexplained.com)
Wiki (eng, "Sorting algorithm") / Wiki (ru, "Алгоритм сортировки") - в англоязычном варианте есть таблица сравнения алгоритмов.
"Comparison of several sorting algorithms" (warp.povusers.org)
"Sorting Algorithms Animations" (toptal.com)
"Sorting algorithms implemented in C++" (codereview.stackexchange.com)
"Sorting Algorithms" (geeksforgeeks.org)
"Sorting algorithms comparison" (ddeville.me)
"Sorting Arrays" (mathbits.com)
VisuAlgo - Sorting (visualgo.net) - что-то типа анимированного курса

"Глупая сортировка и некоторые другие, поумнее" (habrahabr.ru) - обзор сортировок с анимацией
"И снова про сортировки: выбираем лучший алгоритм" (habrahabr.ru)

 

Add new comment

Plain text

  • No HTML tags allowed.
  • Lines and paragraphs break automatically.
  • Web page addresses and email addresses turn into links automatically.