//Основной код

int Length; // длина массива

int* Array; // указатель на начало массива

double Time; // время сортировки в секундах

int Size; // общее количество процессов

int Rank; // номер текущего процесса

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &Size);

MPI_Comm_rank(MPI_COMM_WORLD, &Rank);

MPI_Status Status;

if (Rank == 0) {

// ввод массива

cout << "Length = ";

cin >> Length;

Array = new int[Length];

srand(clock());

for (int i = 0; i < Length; i++)

Array[i] = rand();

// распечатать массив

Print(Array, Length, "\nRandom array:\n\n");

int* Copy = new int[Length];

for (int i = 0; i < Length; i++)

Copy[i] = Array[i];

Time = clock();

QuickSort(Copy, 0, Length - 1);

Time = (clock() - Time) / CLOCKS_PER_SEC;

cout << "Sort time by 1 proc = " << Time << " sec" << endl;

delete[] Copy;

// запуск таймера

Time = clock();

}

int Pos = 0; // позиция первого элемента части исходного массива

int Count = Length; // длина этой части

int* Part = Array; // указатель на начало этой части

int FirstProc = Rank; // первый процесс, сортирующий эту часть

int LastProc = Size - 1; // последний процесс, сортирующий эту часть

// значения по умолчанию соответствуют нулевому процессу

if (Rank != 0) {

MPI_Recv(&Pos, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &Status);

MPI_Recv(&Count, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &Status);

Part = new int[Count];

MPI_Recv(Part, Count, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &Status);

MPI_Recv(&LastProc, 1, MPI_INT, MPI_ANY_SOURCE, 0, MPI_COMM_WORLD, &Status);

}

int Left = 0; // позиция первого элемента

int Right = Count - 1; // позиция последнего элемента

int Middle; // позиция деления на две части

int i = FirstProc + (LastProc - FirstProc + 1) / 2; // первый процесс, сортирующий меньшую часть

int j = LastProc; // последний процесс, сортирующий меньшую часть

while (i > FirstProc) {

Divide(Part, Left, Right, Middle);

int pos; // позиция первого элемента меньшей части

int count; // длина этой части

if (Middle - Left + 1 <= Right - Middle) {

pos = Left;

count = Middle - Left + 1;

Left = Middle + 1;

}

else {

pos = Middle + 1;

count = Right - Middle;

Right = Middle;

}

MPI_Send(&pos, 1, MPI_INT, i, 0, MPI_COMM_WORLD);

MPI_Send(&count, 1, MPI_INT, i, 0, MPI_COMM_WORLD);

MPI_Send(Part + pos, count, MPI_INT, i, 0, MPI_COMM_WORLD);

MPI_Send(&j, 1, MPI_INT, i, 0, MPI_COMM_WORLD);

j = i - 1;

i = FirstProc + (j - FirstProc + 1) / 2;

}

QuickSort(Part, Left, Right);

i = FirstProc + (LastProc - FirstProc + 1) / 2;

while (i > FirstProc) {

int pos;

int count;

MPI_Recv(&pos, 1, MPI_INT, i, 0, MPI_COMM_WORLD, NULL);

MPI_Recv(&count, 1, MPI_INT, i, 0, MPI_COMM_WORLD, NULL);

MPI_Recv(Part + pos, count, MPI_INT, i, 0, MPI_COMM_WORLD, NULL);

i = FirstProc + (i - FirstProc) / 2;

}

if (Rank != 0) {

MPI_Send(&Pos, 1, MPI_INT, Status.MPI_SOURCE, 0, MPI_COMM_WORLD);

MPI_Send(&Count, 1, MPI_INT, Status.MPI_SOURCE, 0, MPI_COMM_WORLD);

MPI_Send(Part, Count, MPI_INT, Status.MPI_SOURCE, 0, MPI_COMM_WORLD);

delete[] Part;

}

else

{

// вывод результатов

Time = (clock() - Time) / CLOCKS_PER_SEC;

//Print(Array, Length, "\nSort array:\n\n");

cout << "Sort time by " << Size << " proc = " << Time << " sec" << endl;

delete[] Array;

}

MPI_Finalize();

//Приложение

Print(int* A, int N, char message[]) {

cout << message;

for (int i = 0; i < N; i++)

cout << "A(" << i << ") = " << A[i] << endl;

}

Divide(int* A, int L, int R, int &M) {

int x = A[L]; M = L;

for (int i = L + 1; i <= R; i++)

if (A[i] < x) {

M++; int temp = A[M]; A[M] = A[i]; A[i] = temp;

}

int temp = A[L]; A[L] = A[M]; A[M] = temp;

}

QuickSort(int* A, int L, int R) {

if (L < R) { int M; Divide(A, L, R, M); QuickSort(A, L, M); QuickSort(A, M + 1, R); }

}