Сети сортировки: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Lira (обсуждение | вклад) (Новая страница: «Сети сортировки») |
Lira (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | Сети сортировки | + | == Описание свойств и структуры алгоритма == |
| + | |||
| + | === Словесное описание алгоритма === | ||
| + | |||
| + | '''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [сеть сортировки простой вставкой], [сеть четно-нечетной перестановки], [сеть четно-нечетного слияния Бетчера] и [сеть битонной сортировки]. К не масштабируемым следует отнести ряд оптимальных с точки зрения времени выполнения сетей для 6, 9, 10, 12 и 16 процессоров <ref>"Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск"</ref>. | ||
| + | |||
| + | === Математическое описание === | ||
| + | |||
| + | Исходные данные: одномерный массив <math>n</math> чисел. | ||
| + | |||
| + | Вычисляемые данные: упорядоченный массив. | ||
| + | |||
| + | === Существующие реализации алгоритма === | ||
| + | |||
| + | |||
| + | == Примечания == | ||
| + | |||
| + | {{примечания}} | ||
Версия 03:48, 7 декабря 2014
Содержание
1 Описание свойств и структуры алгоритма
1.1 Словесное описание алгоритма
Сети сортировки используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [сеть сортировки простой вставкой], [сеть четно-нечетной перестановки], [сеть четно-нечетного слияния Бетчера] и [сеть битонной сортировки]. К не масштабируемым следует отнести ряд оптимальных с точки зрения времени выполнения сетей для 6, 9, 10, 12 и 16 процессоров [1].
1.2 Математическое описание
Исходные данные: одномерный массив [math]n[/math] чисел.
Вычисляемые данные: упорядоченный массив.
1.3 Существующие реализации алгоритма
2 Примечания
- ↑ "Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск"
