Сеть нечетно-четной перестановки: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Lira (обсуждение | вклад) Новая страница: «Сеть нечетно-четной перестановки» |
Lira (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Сеть нечетно-четной перестановки | Сеть нечетно-четной перестановки | ||
== Описание свойств и структуры алгоритма == | |||
=== Словесное описание алгоритма === | |||
Сеть сортировки размером <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 </math> приведён на рисунке | |||
=== Математическое описание === | |||
=== Вычислительное ядро алгоритма === | |||
=== Описание схемы реализации последовательного алгоритма === | |||
=== Последовательная сложность алгоритма === | |||
=== Информационный граф === | |||
=== Описание ресурса параллелизма алгоритма === | |||
=== Описание входных и выходных данных === | |||
=== Свойства алгоритма === | |||
== Программная реализация == | |||
=== Особенности реализации последовательного алгоритма === | |||
=== Описание локальности данных и вычислений === | |||
==== Описание локальности алгоритма ==== | |||
==== Описание локальности реализации алгоритма ==== | |||
===== Описание структуры обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности реализации параллельного алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | |||
==== Описание масштабируемости алгоритма ==== | |||
==== Описание масштабируемости реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | |||
=== Выводы для классов архитектур === | |||
=== Существующие реализации алгоритма === | |||
== Литература == | |||
Версия от 19:24, 9 мая 2019
Сеть нечетно-четной перестановки
Описание свойств и структуры алгоритма
Словесное описание алгоритма
Сеть сортировки размером [math]\displaystyle{ n }[/math] задаёт расписание для упорядочивания [math]\displaystyle{ n }[/math] элементов массива. Сеть нечетно-четной перестановки является масштабируемой, поскольку может быть построена для любого числа элементов [math]\displaystyle{ n \ge 3 }[/math].
Сеть состоит из [math]\displaystyle{ n }[/math] стадий. На стадиях с чётными номерами выполняются операции сравнения-перестановки пар элементов с номерами [math]\displaystyle{ 2*i и 2*i+1 }[/math], на стадиях с нечётными номерами выполняются операции сравнения-перестановки пар элементов с номерами [math]\displaystyle{ 2*i-1 и 2*i }[/math]. Пример для [math]\displaystyle{ n = 4 }[/math] приведён на рисунке