параллельная Bubble сортировка с использованием openmp - PullRequest
Новая
       13

параллельная Bubble сортировка с использованием openmp

3 голосов
/ 08 января 2010

Я пишу код на C ++ для алгоритма сортировки Bubble, и я не знаю, как сделать его параллельным, используя openmp, поэтому, пожалуйста, помогите мне ..... это код: 

#include "stdafx.h"    
#include <iostream>
#include <time.h>
#include <omp.h>
using namespace std;

int a[40001];
void sortArray(int [], int);
int q=0;

int _tmain(int argc, _TCHAR* argv[])
{   
int x=40000;
int values[40000];
for (int i=0;i<x;i++)
{
    values[i]=rand();
}
cout << "Sorting Array .......\n";
clock_t start = clock();
sortArray(values, x);
 cout << "The Array Now Sorted\n";
printf("Elapsed Time : %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
cout << "\n";
}
 void sortArray(int array[], int size)  
{
  bool swap;
   int temp;
  do
  {
   swap = false;
  for (int count = 0; count < (size - 1); count++)
   {
   if (array[count] > array[count + 1])
  {
    temp = array[count];
    array[count] = array[count + 1];
    array[count + 1] = temp;
    swap = true;
  }
  }
  }while (swap);
}

это занимает сейчас около 13 секунд, которые я пытался поставить ## Pragma omp параллельно для перед "for statment" в методе sortArray, и это не имеет никакого значения, это займет около 13 секунд ..... поэтому, пожалуйста, помогите мне как можно быстрее

1 Ответ

6 голосов
/ 08 января 2010

Попробуйте это Параллельная пузырьковая сортировка алгоритм: 

1.  For k = 0 to n-2
2.  If k is even then
3.     for i = 0 to (n/2)-1 do in parallel
4.         If A[2i] > A[2i+1] then
5.             Exchange A[2i] ↔ A[2i+1]
6.  Else
7.     for i = 0 to (n/2)-2 do in parallel
8.         If A[2i+1] > A[2i+2] then
9.             Exchange A[2i+1] ↔ A[2i+2]
10. Next k

Параллельный анализ

Шаги 1-10 - это один большой цикл, который представлен n -1 раз. Следовательно, параллельная временная сложность O (n). Если алгоритм, нечетные шаги нужно (n / 2) - 2 процессора и четные шаги требуют
(n / 2) - 1 процессор. Поэтому для этого требуется O (n) процессоров.

Вы все еще можете использовать проверку флага swap, чтобы остановить процедуру прямо перед Next k.
Конечно, не ожидайте значительного улучшения скорости без сотен физических процессоров:)

...