Сортировка по четным и нечетным дозаторам - Batcher odd–even mergesort

Сортировка по четным и нечетным дозаторам

Визуализация нечетно-четной сети сортировки слиянием с восемью входами
Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${\displaystyle O(\log ^{2}(n))}$ параллельное время
Лучший случай спектакль	${\displaystyle O(\log ^{2}(n))}$ параллельное время
Средний спектакль	${\displaystyle O(\log ^{2}(n))}$ параллельное время
Худший случай космическая сложность	${\displaystyle O(n\log ^{2}(n))}$ непараллельное время

Сортировка нечетных и четных слиянием Батчера общая конструкция, разработанная Кен Батчер за сортировочные сети размера O (п (бревноп)²) и глубиной O ((logп)²), куда п - количество сортируемых элементов. Хотя это не является асимптотически оптимальным, Knuth заключенный в 1998 году в отношении Сеть АКС что "метод Батчера намного лучше, если только п превышает общий объем памяти всех компьютеров на Земле! "^[1]

Его популяризирует второй Камни GPU книга,^[2] как простой способ выполнять достаточно эффективную сортировку на оборудовании для обработки графики.

Псевдокод

Возможны различные рекурсивные и итеративные схемы для вычисления индексов сравниваемых и сортируемых элементов. Это один из итерационных методов генерации индексов для сортировки n элементов:

# примечание: входная последовательность индексируется от 0 до (n-1) для p = 1, 2, 4, 8, ... # пока p  = 1 для j = mod (k, p) to (n-1-k) с размером шага 2k для i = 0 до k-1 с размером шага из 1, если floor ((i + j) / (p * 2)) == floor ((i + j + k) / (p * 2)) сравнить и отсортировать элементы (i + j) и (i + j + л)

Также возможен безрекурсивный расчет индекса узла-партнера.^[3]

Смотрите также

• Bitonic сортировщик

Рекомендации

1. D.E. Knuth. Искусство программирования, Том 3: Сортировка и поиск, Второе издание. Аддисон-Уэсли, 1998. ISBN  0-201-89685-0. Раздел 5.3.4: Сети для сортировки, стр. 219–247.
2. https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter46.html
3. "Сортировка сети из четно-нечетного слияния Batcher: расчет партнера". Ренат Бекболатов. Получено 7 мая 2015.

внешняя ссылка

• Сортировка по четным и нечетным на fh-flensburg.de
• Генератор нечетно-четной сети слияния Генератор сети сортировки на основе слияния нечетных и четных от Interactive Batcher.