SHARE
TWEET

Untitled

a guest Dec 12th, 2018 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // sortOMP.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include <omp.h>
  6. #include <string>
  7. #include <stdio.h>
  8. #include <ctime>
  9. #include <iostream>
  10.  
  11. int tab_size = 1000000;
  12.  
  13. using namespace std;
  14.  
  15.  
  16.  
  17. ////////////////
  18.  
  19. void merge(int *arr, int l, int m, int r)
  20. {
  21.     int i, j, k;
  22.     int n1 = m - l + 1;
  23.     int n2 = r - m;
  24.  
  25.  
  26.     int *L, *R;
  27.     L = (int*)malloc(sizeof(int*)*n1);
  28.     R = (int*)malloc(sizeof(int*)*n2);
  29.  
  30.  
  31.     for (i = 0; i < n1; i++)
  32.         L[i] = arr[l + i];
  33.     for (j = 0; j < n2; j++)
  34.         R[j] = arr[m + 1 + j];
  35.  
  36.     i = 0;
  37.     j = 0;
  38.     k = l;
  39.     while (i < n1 && j < n2)
  40.     {
  41.         if (L[i] <= R[j])
  42.         {
  43.             arr[k] = L[i];
  44.             i++;
  45.         }
  46.         else
  47.         {
  48.             arr[k] = R[j];
  49.             j++;
  50.         }
  51.         k++;
  52.     }
  53.  
  54.  
  55.     while (i < n1)
  56.     {
  57.         arr[k] = L[i];
  58.         i++;
  59.         k++;
  60.     }
  61.  
  62.     while (j < n2)
  63.     {
  64.         arr[k] = R[j];
  65.         j++;
  66.         k++;
  67.     }
  68.     free(R); free(L);
  69. }
  70.  
  71.  
  72. void mergeSort(int *arr, int l, int r)
  73. {
  74.     if (l < r)
  75.     {
  76.         int m = l + (r - l) / 2;
  77.        
  78.         #pragma omp parallel firstprivate(m,l, r) shared(arr) num_threads(4)
  79.         {
  80.             #pragma omp sections nowait
  81.         {
  82.                 #pragma omp section
  83.                 {
  84.  
  85.                     mergeSort(arr, l, m);
  86.                 }
  87.  
  88.                 #pragma omp section
  89.                 {
  90.                     mergeSort(arr, m + 1, r);
  91.                 }
  92.             }
  93.            
  94.            
  95.         }
  96.             merge(arr, l, m, r);
  97.        
  98.     }
  99. }
  100.  
  101.  
  102. void mergeSortSekw(int *arr, int l, int r)
  103. {
  104.     if (l < r)
  105.     {
  106.  
  107.         int m = l + (r - l) / 2;
  108.         mergeSort(arr, l, m);
  109.         mergeSort(arr, m + 1, r);
  110.         merge(arr, l, m, r);
  111.  
  112.     }
  113. }
  114.  
  115. bool isAscending(int *tab, int tab_size)
  116. {
  117.     for (register unsigned int i = 0; i <= tab_size; i++)
  118.     {
  119.         if (tab[i] < tab[i - 1])
  120.             return false;
  121.         else
  122.             return true;
  123.     }
  124.     return true;
  125. }
  126.  
  127. void randomNumbers(int *tab, int tab_size)
  128. {
  129.     srand(time(0));
  130.     register unsigned int n = tab_size;
  131.     while (n--)
  132.     {
  133.         tab[n] = rand();
  134.     }
  135. }
  136.  
  137.  
  138. int main()
  139. {
  140.     int *tab;
  141.     int *t;
  142.     srand(time(NULL));
  143.     tab = (int*)malloc(sizeof(int*)*tab_size);
  144.     t = (int*)malloc(sizeof(int*)*tab_size);
  145.  
  146.     randomNumbers(tab, tab_size);
  147.  
  148.     for (int i = 0; i < tab_size; i++)
  149.     {
  150.         t[i] = tab[i];
  151.     }
  152.    
  153.     clock_t start = clock();
  154.     mergeSort(tab, 0, tab_size - 1);
  155.     clock_t end = clock();
  156.     double elapsed_time = double(end - start) / CLOCKS_PER_SEC;
  157.     printf("Rownolegle: %lf\n", elapsed_time);
  158.     if (isAscending(tab, tab_size)) printf("Tablica posortowana jest prawidlowo\n");
  159.     else printf("Tablica posortowana jest nieprawidlowo\n");
  160.     clock_t start2 = clock();
  161.     mergeSortSekw(t, 0, tab_size - 1);
  162.     clock_t end2 = clock();
  163.     double elapsed_time2 = double(end2 - start2) / CLOCKS_PER_SEC;
  164.     printf("Sekwencyjnie: %lf\n", elapsed_time2);
  165.     if (isAscending(t, tab_size)) printf("Tablica posortowana jest prawidlowo\n");
  166.     else printf("Tablica posortowana jest nieprawidlowo\n");
  167.     //
  168.     //for (int i = 0; i < tab_size; i++)
  169.     //{
  170.     //  printf("Rownolegle: %d \t\t\t Sekwencyjnie: %d\n", tab[i], t[i]);
  171.     //}
  172.  
  173.  
  174.     free(tab); free(t);
  175.     system("Pause");
  176.     return 0;
  177. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top