fork download 
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <omp.h>
  4. #include <chrono>
  5. #include <random>
  6. using namespace std;
  7. void bubble(int *, int);
  8. void parallel_bubble(int *, int);
  9. void swap(int &, int &);
  10. void mergesort(int a[], int i, int j);
  11. void parallel_mergesort(int a[], int i, int j);
  12. void merge(int a[], int i1, int j1, int i2, int j2);
  13.  
  14. void generateRandomArray(int arr[], int size, int seed)
  15. {
  16.     // Create a random number generator engine with the given seed
  17.  
  18.     mt19937 rng(seed);
  19.     // Create a uniform distribution for random integers
  20.     uniform_int_distribution<int> dist(1, 1000);
  21.     // Generate random numbers and fill the array
  22.     for (int i = 0; i < size; ++i)
  23.     {
  24.         arr[i] = dist(rng);
  25.     }
  26. }
  27.  
  28. void parallel_mergesort(int a[], int i, int j)
  29. {
  30.     int mid;
  31.     if (i < j)
  32.     {
  33.         mid = (i + j) / 2;
  34.  
  35. #pragma omp parallel sections
  36.         {
  37.  
  38. #pragma omp section
  39.             {
  40.                 mergesort(a, i, mid);
  41.             }
  42.  
  43. #pragma omp section
  44.             {
  45.                 mergesort(a, mid + 1, j);
  46.             }
  47.         }
  48. #pragma omp barrier
  49. {
  50.         merge(a, i, mid, mid + 1, j);
  51. }
  52.     }
  53. }
  54.  
  55. void mergesort(int a[], int i, int j)
  56. {
  57.     int mid;
  58.     if (i < j)
  59.     {
  60.         mid = (i + j) / 2;
  61.  
  62.         mergesort(a, i, mid);
  63.  
  64.         mergesort(a, mid + 1, j);
  65.     }
  66.  
  67.     merge(a, i, mid, mid + 1, j);
  68. }
  69.  
  70. void merge(int a[], int i1, int j1, int i2, int j2)
  71. {
  72.     int temp[1000];
  73.     int i, j, k;
  74.     i = i1;
  75.     j = i2;
  76.     k = 0;
  77.  
  78.     while (i <= j1 && j <= j2)
  79.     {
  80.         if (a[i] < a[j])
  81.         {
  82.             temp[k++] = a[i++];
  83.         }
  84.         else
  85.         {
  86.             temp[k++] = a[j++];
  87.         }
  88.     }
  89.  
  90.     while (i <= j1)
  91.     {
  92.         temp[k++] = a[i++];
  93.     }
  94.  
  95.     while (j <= j2)
  96.     {
  97.         temp[k++] = a[j++];
  98.     }
  99.  
  100.     for (i = i1, j = 0; i <= j2; i++, j++)
  101.     {
  102.         a[i] = temp[j];
  103.     }
  104. }
  105.  
  106. void parallel_bubble(int *a, int n)
  107. {
  108.  
  109.     for (int i = 0; i < n; i++)
  110.     {
  111.         int first = i % 2;
  112.         for (int j = first; j < n - 1; j += 2)
  113.         {
  114.             if (a[j] > a[j + 1])
  115.             {
  116.                 swap(a[j], a[j + 1]);
  117.             }
  118.         }
  119.     }
  120. }
  121. void bubble(int *a, int n)
  122. {
  123.  
  124.     for (int i = 0; i < n; i++)
  125.     {
  126.         int first = i % 2;
  127. #pragma omp parallel for shared(a, first)
  128.         for (int j = first; j < n - 1; j += 2)
  129.         {
  130.             if (a[j] > a[j + 1])
  131.             {
  132.                 swap(a[j], a[j + 1]);
  133.             }
  134.         }
  135.     }
  136. }
  137.  
  138. void swap(int &a, int &b)
  139. {
  140.     int test;
  141.     test = a;
  142.     a = b;
  143.     b = test;
  144. }
  145.  
  146. int main()
  147. {
  148.  
  149.  
  150.     int n,  a[n],b[n],c[n],d[n], seed = 20;
  151.     cout << "\n enter total no of elements=>";
  152.     cin >> n;
  153.  
  154.     generateRandomArray(a, n, seed);
  155.     auto start = chrono::high_resolution_clock::now();
  156.     bubble(a, n);
  157.     auto end = std::chrono::high_resolution_clock::now();
  158.     cout << endl;
  159.  
  160.     // Calculate the duration
  161.     chrono::duration<double> duration = end - start;
  162.     cout << "\n sorted array is=>  ";
  163.     for (int i = 0; i < n; i++)
  164.     {
  165.         cout << a[i] << "  ";
  166.     }
  167.     // Print the duration
  168.     cout << "Time taken by Sequential Bubble sort:  " << duration.count() << " seconds" << endl;
  169.  
  170.  
  171.  
  172.     generateRandomArray(b, n, seed);
  173.     start = chrono::high_resolution_clock::now();
  174.     parallel_bubble(b, n);
  175.     end = std::chrono::high_resolution_clock::now();
  176.     cout << endl;
  177.  
  178.     // Calculate the duration
  179.     duration = end - start;
  180.     cout << "\n sorted array is=>  ";
  181.     for (int i = 0; i < n; i++)
  182.     {
  183.         cout << b[i] << "  ";
  184.     }
  185.     // Print the duration
  186.     cout << "Time taken by Parallel Bubble sort:  " << duration.count() << " seconds" << endl;
  187.  
  188.  
  189.     generateRandomArray(d, n, seed);
  190.     start = chrono::high_resolution_clock::now();
  191.     parallel_mergesort(d, 0, n-1);
  192.     end = std::chrono::high_resolution_clock::now();
  193.     cout << endl;
  194.  
  195.     // Calculate the duration
  196.     duration = end - start;
  197.     cout << "\n sorted array is=>  ";
  198.     for (int i = 0; i < n; i++)
  199.     {
  200.         cout << d[i] << "  ";
  201.     }
  202.     // Print the duration
  203.     cout << "Time taken by Parallel Merge sort:  " << duration.count() << " seconds" << endl;
  204.  
  205.  
  206. cout<<"Merge Sort--->>>>>>>>>";
  207.     generateRandomArray(c, n, seed);
  208. cout<<"Merge array Sort--->>>>>>>>>";
  209.  
  210.     start = chrono::high_resolution_clock::now();
  211.     mergesort(c, 0, n-1);
  212.     end = std::chrono::high_resolution_clock::now();
  213.     cout << endl;
  214. cout<<"Merge end-->>>>>";
  215.     // Calculate the duration
  216.     duration = end - start;
  217.     cout << "\n sorted array is=>  ";
  218.     for (int i = 0; i < n; i++)
  219.     {
  220.         cout << c[i] << "  ";
  221.     }
  222.     // Print the duration
  223.     cout << "Time taken by Sequential Merge sort:  " << duration.count() << " seconds" << endl;
  224.  
  225.  
  226.  
  227.     return 0;
  228. }
  229.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
10
stdout 
 enter total no of elements=>

 sorted array is=>  36  589  622  641  816  888  892  898  953  955  Time taken by Sequential Bubble sort:  4.47e-07 seconds


 sorted array is=>  36  589  622  641  816  888  892  898  953  955  Time taken by Parallel Bubble sort:  2.41e-07 seconds


 sorted array is=>  589  888  888  888  888  888  888  888  888  888  Time taken by Parallel Merge sort:  9.69e-07 seconds
Merge Sort--->>>>>>>>>Merge array Sort--->>>>>>>>>
Merge end-->>>>>
 sorted array is=>  589  888  888  888  888  888  888  888  888  888  Time taken by Sequential Merge sort:  7.22e-07 seconds
https://ideone.com/dyfHtW
language:
C++14 (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!