Вычисления проводились на процессоре Intel(R) Core(TM) Duo CPU T2300 (1.66GHz); 1024MB RAM.

Результаты экспериментов

 

Размер массива	Последовательный алгоритм	Параллельный алгоритм	Ускорение	Эффективность
100000	0.03	0.019	1.55	0.775
500000	0.2	0.14	1.4	0.7
700000	0.28	0.17	1.64	0.82
1000000	0.41	0.25	1.61	0.805
5000000	2.0	0.76	2.5	1.25

На эффективность работы как последовательного, так и параллельного алгоритма быстрой сортировки сильно влияет результат выбора ведущего элемента. Поэтому для того, чтобы получить неслучайные результаты эксперимента, его нужно проводить несколько раз и усреднять значения для каждого n. Результаты приведены в таблице.

Основные характеристики коммуникационной сети были вычислены экспериментальным способом. На используемой ЭВМ: латентность (как время на передачу сообщения нулевой длины; ~0.0002 с) и достижимая пропускная способность (количество мегабайт в секунду; ~60 МБайт/с), что позволило сравнить практические результаты с теоретическими.

Сравнение теоретических и практических результатов (p=2)

 

Размер массива	Практическое время	Теоретическое время
100000	0.019	0.1
500000	0.14	0.2
700000	0.17	0.23
1000000	0.25	0.3
5000000	0.76	0.9

Как видно из таблицы, наблюдаемое время сортировки несколько превосходит ожидаемое (на приведенных объемах выборки, в среднем, в 1.2 раза). Но мы также видим, что с увеличением объема выборки, полученные в экспериментах значения все ближе приближаются к теоретическим оценкам (т.е. с увеличением объема входных данных, погрешность вычислений уменьшается). Из всех этих данных мы можем сделать вывод о корректности и успешности выполнения поставленной задачи.