Теория и практика параллельных вычислений
Сортировка Шелла
Параллельный алгоритм сортировки Шелла может быть получен как обобщение метода параллельной пузырьковой сортировки. Основное различие состоит в том, что на первых итерациях алгоритма Шелла происходит сравнение пар элементов, которые в исходном наборе данных находятся далеко друг от друга (для упорядочивания таких пар в пузырьковой сортировке может понадобиться достаточно большое количество итераций). Подробное описание параллельного обобщения алгоритма сортировки Шелла можно найти в лекции 9.
Задания и упражнения
- Запустите систему ПараЛаб. Выберите топологию кольцо и установите количество процессоров, равное восьми. Проведите эксперимент по выполнению алгоритма пузырьковой сортировки.
- Установите в окне вычислительного эксперимента топологию гиперкуб и число процессоров, равное восьми.
- Откройте диалоговое окно выбора метода и посмотрите, какие алгоритмы сортировки могут быть выполнены на этой топологии. Выберите метод сортировки Шелла. Закройте окно.
- Проведите вычислительный эксперимент. Сравните количество итераций, выполненных при решении задачи при помощи метода Шелла, с количеством итераций алгоритма пузырьковой сортировки (количество итераций отображается справа в строке состояния). Убедитесь в том, что при выполнении эксперимента с использованием алгоритма Шелла для сортировки массива необходимо выполнить меньшее количество итераций.
- Проведите эксперимент с использованием метода Шелла несколько раз. Убедитесь, что количество итераций не является постоянной величиной и зависит от исходного массива.
