Рассмотрим основные этапы параллельного алгоритма Быстрой сортировки.
1. Нулевой процесс рассылает массив по блокам на
остальные процессы. Блоки принимаются и сортируются Быстрой сортировкой (последовательный
алгоритм быстрой сортировки реализован в функции QuickSort ).
Time = clock(); //начало отсчета времени
MPI_Bcast(&Lenght, 1, MPI_INT, 0, MPI_COMM_WORLD);
int cons=Length/Size; //определяем размер блоков
int* Array2 = new int[cons];
int* Array3 = new int[Length];
MPI_Scatter(&Array[Rank*cons], cons, MPI_INT, Size, cons, MPI_INT, 0, MPI_COMM_WORLD); //рассылка блоков
QuickSort(Array, 0,(cons)-1); //сортировка блоков
2. Процессы отправляют отсортированные блоки нулевому, он их принимает и
последовательно сливает.
for (j=0,z=0,k=0;((j<((cons*i)))&&(z<(cons))) ;) if (Array2[j]
{Array3[k]=Array2[j]; k++;j++;}
else {Array3[k]=Array[z]; k++;z++;};
if (j<(cons)*i) for (int f=j;(f<(cons*i)); f++)
{Array3[k]=Array2[f]; k++;};
if (z<(cons))
for (int f=z;
(f<(cons)); f++)
{Array3[k]=Array[f]; k++;};
