Изменения

Перейти к: навигация, поиск

Обсуждение:PSRS-сортировка

63 байта убрано, 22:16, 9 июня 2014
Нет описания правки
swap(a[i], a[j])
i++ j--
'''while''' (i <tex> \leqslant </tex> j);
'''if''' (n < 100) // если размер массива меньше 100
Каждую итерацию массив делится случайно. На первой итерации при делении на <tex>2</tex> части с меньшими и большими элеменами с разделяющим ведущем пусть длина меньшей части <tex>n1</tex>. Алгоритм отправляет её на другой процессор сортироваться параллельно, а так как она короче, то и досортируется быстрее, значит время её сортировки не учитывается. Длина большей части <tex>N-n1</tex>, с этой частью мы проделываем точно такую же итерацию с разделителем <tex>n2</tex>. И так далее до момента, когда число свободных процессоров закончится, то есть до разделителя <tex>nk</tex>. Где <tex>[p / 100]=2^k</tex>.
<tex>T=(N+(N-n1)+(N-n1-n2)+...+(N-n1-...-nk))*t</tex>, где <tex>t</tex> - время перестановки.
77
правок

Навигация