Просмотр кода страницы Сеть нечетно-четной перестановки

Сеть нечетно-четной перестановки

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

=== Словесное описание алгоритма ===
Сеть сортировки размером <math>n</math> задаёт расписание для упорядочивания <math>n</math> элементов массива.
Сеть нечетно-четной перестановки является масштабируемой, поскольку может быть построена для любого числа элементов <math>n \ge 3</math>.

Сеть состоит из <math>n</math> стадий.
На стадиях с чётными номерами выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i и 2*i+1 </math>, на стадиях с нечётными номерами 
выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i-1 и 2*i </math>. Пример для <math> n = 4, 5 </math> приведён на рисунках 1 и 2.

[[Файл:pic_EvenOdd4.png|center|thumb|800px|Рисунок 1. Сеть чётно-нечетной перестановки для 4 элементов]] [[Файл:pic_EvenOdd5.png|center|thumb|800px|Рисунок 2. Сеть чётно-нечетной перестановки для 5 элементов]]

=== Математическое описание ===
=== Вычислительное ядро алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
=== Описание входных и выходных данных ===
=== Свойства алгоритма ===
== Программная реализация ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
==== Описание локальности алгоритма ====
==== Описание локальности реализации алгоритма ====
===== Описание структуры обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Описание масштабируемости алгоритма ====
==== Описание масштабируемости реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==