7. if id is odd then
8. compare-exchange_min(id+1);
9. else
10. compare-exchange_max(id-1);
11. if i is even then
12. if id is even then
13. compare-exchange_min(id+1);
14. else
15. compare-exchange_max(id-1);
16. end for
17. end ODD-EVEN_PAR
Әрбір фазада орындалатын қадамдарға Q(1) уақыт кетеді. Барлығы n фаза
болса, параллельді алгоритмнің орындалуына Q(n) уақыт кетеді екен.
Параллельді әдіске қысқаша сипаттама
p – процессорлар саны, n – сұрыпталатын тізбектің ұзындығы, мұндағы p
Бастапқыда, әрбір процессор үшін n/p элементтен тұратын блок
тағайындалады, ол бұл элементтерден іштей Q((n/p)*log(n/p)) уақытта
сұрыптап шығады. Мұнан кейін процессорлар р фазыдан өтіп шығады (p/2
тақ және p/2 жұп), яғни «салыстыру-бөлу» (compare-split) операциясын
орындайды. Сақинадағы процессорлар бір-біріне элементтерін алмастырады.
Нәтижесніде әрбір процессорда өз элементтері және көрші процессордың
элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор
элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы – екінші
жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң тізбек
сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p) салыстыру
орындалады және Q(n/p) уақыт жұмсалады.
Достарыңызбен бөлісу: 
