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

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

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

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

Сеть сортировки размером [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, 5 }[/math] приведён на рисунках 1 и 2.

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

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