Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Классификация алгоритмов сортировки).pdf

После обхода всего исходного массива мы получим число вхождений каждого из элементов в массив. Затем следует лишь записать в исходный массив нужное количество элементов каждого вида. Например, если выяснилось, что из десяти полученных учеником оценок 2 двойки, 3 тройки, 4 четверки и одна пятерка, то можно просто переписать исходный массив как «2-2-3-3-3-4-4-4-4-5».

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

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

7. Параллельный алгоритм сортировки

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

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

Чтобы понять принцип работы алгоритма, нужно вспомнить, что при классической сортировке слиянием мы делим массив на две половины, каждую из которых сортируем отдельно. В нашем случае мы поступаем точно также, однако делим массив не на две части по количеству элементов, а следующим образом – «нечетные элементы (1-й, 3-й, 5-й, и т.д.) направляются в первую половину некоего временного массива, а четные элементы (2-й, 4-й, 6-й, и т.д.) направляются во вторую половину некоего временного массива». Далее, как и в случае сортировки слиянием, каждую из половинок нужно отсортировать отдельно – как правило, это делается вызовом нашей же сортировки рекурсивно (обратим внимание, что здесь мы и получаем выигрыш в параллельном выполнении, так как каждую половинку можно сортировать параллельно, на своем ядре процессора). Затем, после того, как обе половинки окажутся отсортированными, необходимо их объединить. Это происходит следующим образом – берутся соответствующие элементы из каждой половинки (1-е, 2-е, 3-е, и т.д.), и в зависимости от их значений выстраиваются на четные и нечетные места итогового массива.

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

1. Добавить в массив необходимое число незначащих элементов, чтобы его размер стал степенью двойки. При сортировке по возрастанию можно добавить необходимое число элементов, больше максимального, которые потом убрать;
2. Вспомнить, что любое число можно представить как сумму степеней двойки. Например, если у нас в массиве 112 элементов, то 112 можно представить как 64+32+16. Таким образом, мы можем отсортировать первые 64 элемента, затем следующие 32, и конечные 16. В итоге нам нужно будет объединить эти три массива.

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

Для данного алгоритма в [10] были проведены замеры скорости. Тестировались случайные данные различной длины (от 100 до 1.000.000.000 элементов массива, являющихся беззнаковыми целыми числами). Сам алгоритм выполнялся на различном числе потоков (от 4 до 16) на 8-ядерном компьютере Intel Core i7-3770 (4 физических ядра, и 8 виртуальных). Результаты исследования приведены ниже:

Таблица 1

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

• Если число элементов невелико, то параллельная сортировка выполняется хуже обычной быстрой сортировки;
• При увеличении числа элементов, параллельная сортировка становится быстрее классической, причем чем больше элементов сортируется, тем на большее число потоков лучшее ее делить;
• Попытка использовать больше потоков (16), чем есть ядер в системе (8) приводит лишь к ухудшению временных характеристик (хотя и не очень сильных).

Заключение

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

Однако уже сейчас можно понять, что идеального метода сортировки не существует. Каждый из них (кроме тех, что описаны как непрактичные) имеет свои области применения. Даже медленные алгоритмы вроде сортировки пузырьком могут служить в качестве учебного пособия при обучении по данной теме. Хотя основные методы сортировки были изобретены довольно давно, но нельзя сказать, что данная область остановилась в развитии. Во-первых, иногда (хотя и не так быстро, как раньше) все еще появляются новые методы – например, TimSort в 2002 году. Кроме того, проводятся исследования относительно того, какие алгоритмы сортировки лучше всего можно распараллелить на несколько ядер или процессоров.