Сети сортировки: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Lira (обсуждение | вклад) Нет описания правки |
Lira (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
Позже этот факт получил объяснение{{sfn|Иванов|1985|с=13}}. | |||
=== еее Существующие реализации алгоритма === | |||
== Литература == | |||
* {{книга | |||
| автор = Иванов И. И. | |||
| заглавие = О необходимости всего сущего | |||
<!-- другие необходимые параметры шаблона «книга» --> | |||
| год = 1985 | |||
| ref = Иванов | |||
}} | |||
Версия от 00:57, 7 декабря 2014
Описание свойств и структуры алгоритма
Словесное описание алгоритма
Сети сортировки используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [сеть сортировки простой вставкой], [сеть четно-нечетной перестановки], [сеть четно-нечетного слияния Бетчера] и [сеть битонной сортировки]. К не масштабируемым следует отнести ряд оптимальных с точки зрения времени выполнения сетей для 6, 9, 10, 12 и 16 процессоров [1].
Математическое описание
Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел.
Вычисляемые данные: упорядоченный массив.
Существующие реализации алгоритма
Позже этот факт получил объяснениеШаблон:Sfn.
еее Существующие реализации алгоритма
Литература
* Шаблон:Книга
Примечания
- ↑ "Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск"