Advertisement
DavidsonDFGL

InsertionSort Parallel (OpenMP)

Aug 29th, 2014
528
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.22 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <omp.h>
  3. //#include <time.h>
  4. #include <stdlib.h>
  5. #include <math.h>
  6.  
  7. #define DEBUG  0
  8.  
  9. #define NUM_THREAD  1
  10. #define VECT_LEN    32000
  11.  
  12. void decrescente(int v[VECT_LEN])
  13. {
  14.     for(int i = 0; i < VECT_LEN; i++)
  15.     {
  16.     v[i] = VECT_LEN - 1 - i;
  17.   }
  18. }
  19.  
  20. void insertionSort(int v[VECT_LEN], int index, int end)
  21. {
  22.     for(int i = index; i < end; i++)
  23.     {
  24.     int tmp = v[i];
  25.     int j = i - 1;
  26.          
  27.     while ((j >= index) && (v[j] > tmp))
  28.     {
  29.       v[j + 1] = v[j];
  30.       j--;
  31.     }
  32.     v[j + 1] = tmp;  
  33.   }
  34. }
  35.  
  36. int main()
  37. {
  38.     int v[VECT_LEN];
  39.     decrescente(v);
  40.  
  41.     /* Ordenação paralela (multithread), o array de 12 elementos
  42.      * é ordenado em 3 threads, cada uma ordenando 4 elementos por
  43.      * vez. */
  44.    
  45.     int blockSize = VECT_LEN / NUM_THREAD;
  46.     for(int i=0; i<(int)log2(NUM_THREAD)+1; i++)
  47.     {
  48.         omp_set_num_threads(NUM_THREAD / (int)( pow(2.0,(double)i) ) );
  49.  
  50.         #pragma omp parallel
  51.         {
  52.             int actualThread = omp_get_thread_num();
  53.             insertionSort( v, actualThread*blockSize, ((actualThread*blockSize)+blockSize) );
  54.         }
  55.  
  56.         blockSize <<= 1;
  57.     }
  58.  
  59. #if DEBUG == 1
  60.     printf("[ ");
  61.   for(int i = 0; i < VECT_LEN; i++)
  62.   {
  63.     printf("%d ", v[i]);
  64.   }
  65.   printf("] \n");
  66. #endif
  67.  
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement