Теория и практика параллельных вычислений

         

Быстрая сортировка


Алгоритм быстрой сортировки основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности. При параллельном обобщении алгоритма обеспечивается отношение упорядоченности между элементами сортируемого набора, расположенными на процессорах, соседних в структуре гиперкуба. В материалах лекции 9 вы можете найти подробное описание алгоритма быстрой сортировки.

Задания и упражнения

  1. Запустите систему ПараЛаб. В появившемся окне вычислительного эксперимента установите топологию гиперкуб и количество процессоров, равное восьми.
  2. Выполните три последовательных эксперимента с использованием трех различных алгоритмов сортировки: сортировки пузырьком, сортировки Шелла и быстрой сортировки. Сравните временные характеристики алгоритмов, которые отображаются в правой нижней части окна. Убедитесь в том, что у быстрой сортировки наименьшее время выполнения алгоритма и время передачи данных.
  3. Измените объем исходных данных (выполните команду Параметры задачи пункта меню Задача). Снова проведите эксперименты. Сравните временные характеристики алгоритмов.
  4. Измените количество процессоров (выполните команду Количество процессоров пункта меню Система). Проведите вычислительные эксперименты и сравните временные характеристики.



Содержание раздела