Рассмотрим алгоритм последовательной сортировки пузыроком:

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. В улучшенном варианте сортировки проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны (что означает — массив отсортирован). При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

Вход: массив a, состоящий из элементов a[1], a[2], ..., a[n]

BUBBLE_SORT(n)
{
  for (i=n-1; i < 1; i--)
    for (j=1; j < i; j++)
      compare_exchange(a[j], a[j+1]);
}

Итерация внутреннего цикла выполняется за время O(n), всего выполняемтся O(n) итераций. Значит сложность пузырьковой сортировки O(n²).

Рассмотрим алгоритм четной-нечетной перестановки:

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

Он также сортирует n элементов за n итераций (n - четно), однако правила итераций различаются в зависимости от четности или нечетности номера итерации и, кроме того, каждая из итераций требует n/2 операций сравнения-обмена.

Пусть (a1,a2, ...,an) - последовательность, которую нужно отсортировать. На итерациях с нечетными итерациями элементы с нечетными индексами сравниваются с их правыми соседями, и если они не находятся в нужном порядке, они меняются местами (т.е. сравниваются пары (a1, а2), (a3, a4), (an-1,an) и, при необходимости, обмениваются (принимая, что n четно). Точно так же в течение четной фазы элементы с четными индексами сравниваются с их правыми соседями (т.е. сравниваются пары (а2, a3), (a4, a5), (an-2,an-1)), и если они находятся не в порядке сортировки, их меняют местами. После n фазы нечетно-четных перестановок последовательность отсортирована. Каждая фаза алгоритма (и нечетная, и четная) требует O(n) сравнений, а всего n фаз; таким образом, последовательная сложность алгоритма - O(n²).

ODD_EVEN(n)
{
   for (i=1; i    {
   if (i%2==1)                 // нечетная итерация
      for (j=0; j < n/2-1; j++)
       compare_exchange(a[2j+1],a[2j+2]);
   if (i%2==0)                 // четная итерация
      for (j=1; j < n/2-1; j++)
       compare_exchange(a[2j],a[2j+1]);
   }
}

Рассмотрим параллельный алгоритм четной-нечетной перестановки:

Для каждой итерации алгоритма операции сравнения-обмена для всех пар элементов являются независимыми и выполняются одновременно. Рассмотрим случай, когда число процессоров равно числу элементов . Пусть p=n - число процессоров (а также число элементов, которые нужно сортировать). Предположим, что вычислительная система имеет топологию кольца. Пусть далее элементы ai i = 1, 2, ... , n, первоначально располагаются на процессорах pi, i = 1, 2, ... , n. В течение нечетной итерации каждый процессор, который имеет нечетный номер, производит сравнение-обмен своего элемента с элементом, находящимся на процессоре-соседе справа. Аналогично, в течение четной итерации каждый процессор с четным номером производит сравнение-обмен своего элемента с элементом правого соседа.

ODD_EVEN_PAR(n)
{
  id = GetProcId
  for (i=1; i   {
    if (i%2 == 1)// нечетная итерация
      if (id%2 == 1)// нечетный номер процессора
          compare_exchange_min(id+1);// сравнение-обмен с элементом на процессоре-соседе справа
      else
          compare_exchange_max(id-1); // сравнение-обмен с элементом на процессоре-соседе слева
    if (i%2 == 0) // четная итерация
      if(id%2 == 0) // четный номер процессора
          compare_exchange_min(id+1); // сравнение-обмен с элементом на процессоре-соседе справа
      else
          compare_exchange_max(id-1); // сравнение-обмен с элементом на процессоре-соседе слева
  }
}

В течение каждой фазы алгоритма и нечетные и четные процессоры выполняют шаг сравнения- обмена с их правыми соседями. Это требует Q(1) времени. Общее количество таких фаз - n; таким образом, параллельное время выполнения этой формулировки - Q(n).

Рассмотрим теперь случай, когда число процессоров p меньше, чем число элементов n. Тогда каждый из процессов получает свой блок банных n/p, который сортирует за время Q((n/p)*log(n/p)). После этого процессоры проходят p фаз (р/2 чётных и р/2 нечётных) и делают сравнивания-разбиения: смежные процессоры передают друг другу свои данные и внутренне их сортируют (на каждой паре процессоров получаем одинаковые массивы). После этого удвоенный массив делится на 2 части: левый процессор обрабатывает далее только левую часть (с меньшими значениями данных), а правый - только правую (с большими значениями данных). По окончанию p итераций получаем отсортированный массив.