Сети сортировки

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

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

Сети сортировки используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести сеть сортировки простой вставкой, сеть четно-нечетной перестановки, сеть четно-нечетного слияния Бетчера и сеть битонной сортировки. К не масштабируемым следует отнести ряд оптимальных (с точки зрения времени выполнения) сетей для 6, 9, 10, 12 и 16 процессоров [1].

Математическое описание

Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел.

Вычисляемые данные: упорядоченный массив.

Литература

1. Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.