Методы повышения эффективности алгоритмов сортировки

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

В данной статье рассмотрена Корневая сортировка (Поразрядная сортировка, RadixSort) и ее сравнение с «Быстрой» сортировкой (QuickSort).

Целью данной работы является поиск методов повышения эффективности использования аппаратных ресурсов при решении задач связанных с сортировкой больших массивов данных.

RadixSort - алгоритм сортировки без сравнений. Является наиболее эффективным алгоритмом из всех существующих на сегодняшний день. Его сложность, как в наилучшем, так и в наихудшем случае равна O(N) (N - число элементов массива), то есть, сложность алгоритма линейна. Сортировка происходит по разрядам чисел входного массива, то есть поочередно на каждом цикле числа проверяются по первому разряду, на следующем - по второму разряду и так далее, пока не будет получен отсортированный массив чисел. Это первый тип корневой сортировки - LSD, с младших разрядов, до старших. Он используется для дальнейшей сравнительной характеристики, так как больше всего он подходит для сортировки чисел. Второй тип RadixSort - MSD. Он противоположен LSD - сортировка идет со старших разрядов к младшим. И этот тип используется для лексикографической сортировки строк. После каждого прохода по массиву получаются так называемые «стопки» элементов, которые представляют из себя массив чисел, выбранных из общего множества по принципу равенства цифр в определенном разряде. Из них в дальнейших проходах берутся числа, что в итоге приводит к тому, что в конце получается коллекция «стопок», при записи элементов которых по очереди получится готовый отсортированный массив. Поэтому этот алгоритм и не использует сравнений, так как происходят постепенные перекладывания элементов до достижения нужного результата. Недостаток RadixSort - большое потребление памяти, чему в данной статье тоже будет уделено внимание.

QuickSort - это алгоритм сортировки со сравнениями, который является одним из самых быстрых среди существующих алгоритмов. Его сложность O(N*log(N)) (N - число элементов массива). «Быстрая» сортировка рекурсивна. Каждый новый проход она делит массив еще на два массива, и для каждой части вызывает сама себя, таким образом постепенно отсортировывая весь массив. Существует множество видов «быстрой» сортировки, в основном они различаются выбором опорного элемента - элемента, относительно которого сравниваются остальные числа. Для данной статьи использовался вариант QuickSort со средним в массиве опорным элементом. Сравниваются числа до среднего числа и после него с самим средним числом. Если левее него числа больше, они переносятся вправо, и, если правее него числа меньше, меняем их с неугодными числами в левой части. Потом делим массив относительно опорного элемента и повторяем для обеих частей. При самом худшем варианте QuickSort будет сравнима по скорости с Bubble Sort, и разделения массива будут до одного элемента.

Теперь разберем вопрос о занимаемом объеме памяти при применении этих сортировок. Как уже было сказано выше, недостаток RadixSort - это большое потребление памяти, вследствие того, что нам на каждой итерации нужно хранить 10 списков, в которых хранятся «стопки» чисел. Чтобы оптимизировать этот процесс можно использовать динамические массивы, например, в языке программирования C++ это vector:

vector<int> *Temp = new vector<int>[10];

Для данной задачи создается массив динамических массивов (векторов), так как количество цифр известно, а вот размер сортируемых данных - нет. Из полученных «стопок» копируются элементы в исходный массив, а динамические массивы, хранящие их, очищаем до следующей итерации, что дает нам дополнительный объем памяти.

for (size_t j = 0; j < 10; j++)

{Temp[j].resize(0);}

После отработки алгоритма освобождается память, занятая под «стопки».

delete[] Temp;

рекурсивный алгоритм сортировка массив

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

Рассмотрим быстродействие данных сортировок на разных входных данных, а именно - размер массива и диапазон значений. Размер массива будем брать довольно большой, так как разницы по времени при сортировке маленького массива данных видно не будет.

Входные параметры будут изменяться так: на вход даются случайные числа; отсортированный, или почти отсортированный массив; числа в обратном порядке следования (например 3, 2, 1, 0); массив с малым количеством уникальных элементов. По размерам возьмем массивы из 1000000: 200000; 3000000 и 4000000 элементов, чтобы проследить линейное увеличение времени работы RadixSort. Значения в таблицы будут записываться в миллисекундах. Замеры будут производиться 50 раз, в таблицу заносится среднее значение. Данные замеры нельзя считать точными, так как время отработки алгоритма зависит от состояния системы на данный момент, а оно имеет свойство изменяться.

Корневая сортировка:

Табл. 1

«Быстрая» сортировка:

Табл. 2

Видно, что при случайных числах действительно видна линейная зависимость времени работы от количества сортируемых элементов в RadixSort. Время работы «быстрой» и корневой сортировок приблизительно равно.

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

При малом количестве уникальных элементов, которые были выбраны от 0 до 9, у корневой сортировки заметно возрастание скорости, что говорит о ее зависимости от количества разрядов сортируемых чисел - чем их меньше, тем быстрее проходит сортировка. Процесс сортировки RadixSort занимает то же время, что и «быстрая» сортировка.

В итоге можно сказать, что корневая сортировка хоть и может проигрывать в скорости при особых входных данных, но является более стабильной сортировкой, чем QuickSort, без худшего случая, а также может превосходить «быструю» сортировку при правильной оптимизации, а также на числах с малым количеством разрядов. Единственной проблемой является затрачиваемый объем памяти. Использование динамических массивов и своевременное освобождение памяти значительно улучшает эффективность работы алгоритма и значительно уменьшает объем памяти, потребляемый при работе сортировки.

Список литературы

1) Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона [Электронный ресурс]: учебное пособие. -- Электрон. дан. -- М.: ДМК Пресс, 2010.

2) Павловская Т.А. С/С++. Программирование на языке высокого уровня. СПб.: Питер, 2010.

3) Информационный ресурс Wikipedia.

Размещено на Allbest.ru