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

 sorted array is=>  2  36  37  42  117  179  185  194  240  253  255  269  273  273  316  379  448  454  475  478  493  519  562  576  589  622  632  641  658  673  692  719  736  752  771  776  783  784  816  817  840  842  851  858  867  888  892  898  907  930  950  951  953  955  988  Time taken by Sequential Bubble sort:  4.141e-06 seconds


 sorted array is=>  2  36  37  42  117  179  185  194  240  253  255  269  273  273  316  379  448  454  475  478  493  519  562  576  589  622  632  641  658  673  692  719  736  752  771  776  783  784  816  817  840  842  851  858  867  888  892  898  907  930  950  951  953  955  988  Time taken by Parallel Bubble sort:  3.369e-06 seconds


 sorted array is=>  2  36  37  42  117  179  185  194  240  253  255  269  273  273  316  379  448  454  475  478  493  519  562  576  589  622  632  641  658  673  692  719  736  752  771  776  783  784  816  817  840  842  851  858  867  888  892  898  907  930  950  951  953  955  988  Time taken by Parallel Merge sort:  3.117e-06 seconds
Merge Sort--->>>>>>>>>Merge array Sort--->>>>>>>>>
Merge end-->>>>>
 sorted array is=>  2  36  37  42  117  179  185  194  240  253  255  269  273  273  316  379  448  454  475  478  493  519  562  576  589  622  632  641  658  673  692  719  736  752  771  776  783  784  816  817  840  842  851  858  867  888  892  898  907  930  950  951  953  955  988  Time taken by Sequential Merge sort:  2.503e-06 seconds
https://ideone.com/HDg8n1
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!