Сортировка пузырьком

Постановка задачи

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

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

Метод решения

Последовательный алгоритм пузырьковой сортировки сравнивает и обменивает соседние элементы в последовательности, которую нужно отсортировать. Для последовательности (a1, a2, ..., an) алгоритм сначала выполняет n-1 базовых операций "сравнения-обмена" для последовательных пар элементов (a1, a2), (a2, a3), ..., (an-1, an). В результате после первой итерации алгоритма самый большой элемент перемещается ("всплывает") в конец последовательности. Далее последний элемент в преобразованной последовательности может быть исключен из рассмотрения, и описанная выше процедура применяется к оставшейся части последовательности (a'1, a'2, ..., a'n-1). Как можно увидеть, последовательность будет отсортирована после n-1 итерации.

Параллельная схема

Метод чет-нечетной перестановки:

Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания – сравнение пар значений упорядочиваемого набора данных происходит строго последовательно. В связи с этим для параллельного применения обычно используется не сам этот алгоритм, а его мо-дификация, известная в литературе как метод чет-нечетной перестановки (odd-even transposition) . Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или не-четными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами. Таким образом, на всех нечетных итерациях сравниваются пары (a1, a2), (a3, a3), ..., (an–1,an) (при четном n), а на четных итерациях обрабатываются элементы (a2, a3), (a4, a5), ..., (an–2,an–1). После n-кратного повторения итераций сортировки исходный набор данных оказывается упорядоченным.

Блочный алгоритм:

Рассмотрим ситуацию, когда количество вычислительных элементов является меньшим числа упорядочиваемых значений (p < n). Разделим сортируемый массив на блоки данных размера n/p. На первом этапе параллельного метода пузырьковой сортировки каждый вычислительный элемент выполняет сортировку одного из блоков данных при помощи какого-либо быстрого алгоритма; эти действия могут быть выполнены параллельно. На следующем этапе выполняется параллельный алгоритм чет-нечетной перестановки над блоками данных:

-на четных итерациях алгоритма вычислительные элементы с четными индексами 2i выполняют операцию «Сравнить и разделить» для двух упорядоченных блоков с номерами 2i и 2i+1,

-на нечетных итерациях алгоритма вычислительные элементы с не-четными индексами 2i+1 выполняют операцию «Сравнить и разделить» для двух упорядоченных блоков с номерами 2i+1 и 2i+2.

После выполнения p итераций чет-нечетной перестановки исходный массив оказывается упорядоченным.

Анализ эффективности

Метод чет-нечетной перестановки:

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

Для сортировки массива данных методом чет-нечетной перестановки требуется выполнение n итераций алгоритма, на каждой из которых параллельно выполняется сравнение n/2 пар значений. Значит, время выполнения вычислений составляет:

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

Если учесть латентность памяти, то время доступа к памяти можно получить по следующей формуле:

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

где δ есть накладные расходы на организацию параллельности на каждой итерации алгоритма.

где t есть время выполнения базовой операции сортировки.

где b есть эффективная скорость доступа к оперативной памяти.

Для более точной оценки необходимо учесть частоту кэш-промахов γ:

Блочный алгоритм:

Определим теперь сложность блочность алгоритма упорядочивания данных. Как отмечалось ранее, на начальной стадии работы метода каждый процессор проводит упорядочивание своих блоков данных (размер блоков при равномерном распределении данных является равным n/p). Трудоемкость начальной стадии вычислений можно определить выражением вида:

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

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

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