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

Последовательная схема алгоритма

Среднее количество сравнений сортировке пузырьком равно O(n^2). Следовательно трудоемкость применения последовательного алгоритма сортировки будет O(n^2).

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

Длительность операций передач данных между процессорами полностью определяется физической топологией вычислительной сети. Если логически-соседние процессоры, участвующие в выполнении операций "сравнить и разделить", являются близкими фактически (например, для линейки или кольца эти процессоры имеют прямые линии связи), общая коммуникационная сложность алгоритма пропорциональна количеству упорядочиваемых данных, т.е. n. Вычислительная трудоемкость алгоритма определяется выражением Tp=(n/p)log(n/p)+2n, где первая часть соотношения учитывает сложность первоначальной сортировки блоков, а вторая величина задает общее количество операций для слияния блоков в ходе исполнения операций "сравнить и разделить" (слияние двух блоков требует 2(n/p) операций, всего выполняется p итераций сортировки). С учетом данной оценки показатели эффективности параллельного алгоритма имеют вид: Sp=[nlogn]/[(n/p)log(n/p)+2n], Ep=[nlogn]/p[(n/p)log(n/p)+2n] Анализ выражений показывает, что если количество процессоров совпадает с числом сортируемых данных (т.е. p=n ), эффективность использования процессоров падает с ростом n; получение асимптотически ненулевого значения показателя Ep может быть обеспечено при количестве процессоров, пропорциональных величине log n. С учетом трудоемкости коммуникационных действий общее время выполнения параллельного алгоритма сортировки определяется следующим выражением (t-время выполнения базовой операции сортировки): T_p=((n/p)log₂(n/p)+2n)t+p(a+w(n/p)/b)
где α – латентность, β – пропускная способность сети передачи данных, а w есть размер элемента упорядочиваемых данных в байтах.

Быстрая сортировка

Последовательная схема алгоритма

Эффективность быстрой сортировки в значительной степени определяется успешностью выбора ведущих элементов при формировании блоков. В худшем случае трудоемкость метода имеет тот же порядок сложности, что и пузырьковая сортировка (т.е. O(n^2) ). При оптимальном выборе ведущих элементов, когда разделение каждого блока происходит на равные по размеру части, трудоемкость алгоритма совпадает с быстродействием наиболее эффективных способов сортировки (O(nlog n)). В среднем случае количество операций, выполняемых алгоритмом быстрой сортировки, определяется выражением : T=1.4nlogn.

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

Эффективность параллельного метода быстрой сортировки, как и в последовательном варианте, во многом зависит от успешности выбора значений ведущих элементов. Определение общего правила для выбора этих значений не представляется возможным; сложность такого выбора может быть снижена, если выполнить упорядочение локальных блоков процессоров перед началом сортировки и обеспечить однородное распределение сортируемых данных между процессорами вычислительной системы. Длительность выполняемых операций передачи данных определяется операцией рассылки ведущего элемента на каждой итерации сортировки - общее количество межпроцессорных обменов для этой операции на N-мерном гиперкубе может быть ограничено оценкой ∑i=N(N+1)/2~log2p и взаимообменом частей блоков между соседними парами процессоров – общее количество таких передач совпадает с количеством итераций сортировки, т.е. равно log p, объем передаваемых данных не превышает удвоенного объема процессорного блока, т.е. ограничен величиной 2n/p. Вычислительная трудоемкость метода обуславливается сложностью локальной сортировки процессорных блоков, временем выбора ведущих элементов и сложностью разделения блоков, что в целом может быть выражено при помощи соотношения: T1=(n/p)log(n/p)+ log p + log(n/p)log p (при построении данной оценки предполагалось, что для выбора значения ведущего элемента при упорядоченности процессорных блоков данных достаточно одной операции).
Общая трудоемкость алгоритма: [2(n/p)(log₂p) + (n/p)log₂(n/p)]*t + (α+w/β)(log₂p)^2 + (α+w(n/2p)/β)(log₂p)