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

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

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

1.1 Словесное описание алгоритма

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

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

Рисунок 1. Сеть чётно-нечетной перестановки для 4 элементов

Рисунок 2. Сеть чётно-нечетной перестановки для 5 элементов