fork download
copy 
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. #include <vector>
  5. #include <chrono>
  6. #include <omp.h>
  7.  
  8. using namespace std;
  9. using namespace std::chrono;
  10.  
  11. // Function generating a random array of given length
  12. vector<int> randomArray(int length) {
  13.     vector<int> arr(length);
  14.     srand(time(0));
  15.     for (int i = 0; i < length; ++i) {
  16.         arr[i] = rand() % 1000; // Generating random numbers between 0 and 999
  17.     }
  18.     return arr;
  19. }
  20.  
  21. // Bubble Sort in Serial mode
  22. void bubbleSortSerial(vector<int>& arr) {
  23.     int n = arr.size();
  24.     for (int i = 0; i < n - 1; ++i) {
  25.         for (int j = 0; j < n - i - 1; ++j) {
  26.             if (arr[j] > arr[j + 1]) {
  27.                 swap(arr[j], arr[j + 1]);
  28.             }
  29.         }
  30.     }
  31. }
  32.  
  33. // Bubble Sort in Parallel mode
  34. void bubbleSortParallel(vector<int>& arr) {
  35.     int n = arr.size();
  36. #pragma omp parallel for
  37.     for (int i = 0; i < n - 1; ++i) {
  38.         for (int j = 0; j < n - i - 1; ++j) {
  39.             if (arr[j] > arr[j + 1]) {
  40.                 swap(arr[j], arr[j + 1]);
  41.             }
  42.         }
  43.     }
  44. }
  45.  
  46. // Insertion Sort in Serial mode
  47. void insertionSortSerial(vector<int>& arr) {
  48.     int n = arr.size();
  49.     for (int i = 1; i < n; ++i) {
  50.         int key = arr[i];
  51.         int j = i - 1;
  52.         while (j >= 0 && arr[j] > key) {
  53.             arr[j + 1] = arr[j];
  54.             --j;
  55.         }
  56.         arr[j + 1] = key;
  57.     }
  58. }
  59.  
  60. // Insertion Sort in Parallel mode
  61. void insertionSortParallel(vector<int>& arr) {
  62.     int n = arr.size();
  63. #pragma omp parallel for
  64.     for (int i = 1; i < n; ++i) {
  65.         int key = arr[i];
  66.         int j = i - 1;
  67.         while (j >= 0 && arr[j] > key) {
  68.             arr[j + 1] = arr[j];
  69.             --j;
  70.         }
  71.         arr[j + 1] = key;
  72.     }
  73. }
  74.  
  75. // Merge function in serial mode
  76. void mergeSerial(vector<int>& arr, int left, int mid, int right) {
  77.     int n = mid - left + 1;
  78.     int m = right - mid;
  79.     vector<int> L(n), R(m);
  80.     for (int i = 0; i < n; ++i)
  81.         L[i] = arr[left + i];
  82.     for (int j = 0; j < m; ++j)
  83.         R[j] = arr[m + 1 + j];
  84.     int i = 0, j = 0, k = left;
  85.     while (i < n && j < m) {
  86.         if (L[i] <= R[j]) {
  87.             arr[k] = L[i];
  88.             ++i;
  89.         }
  90.         else {
  91.             arr[k] = R[j];
  92.             ++j;
  93.         }
  94.         ++k;
  95.     }
  96.     while (i < n) {
  97.         arr[k] = L[i];
  98.         ++i;
  99.         ++k;
  100.     }
  101.     while (j < m) {
  102.         arr[k] = R[j];
  103.         ++j;
  104.         ++k;
  105.     }
  106. }
  107.  
  108. // Merge sort in serial mode
  109. void mergeSortSerial(vector<int>& arr, int left, int right) {
  110.     if (left >= right) return;
  111.     int mid = left + (right - left) / 2;
  112.     mergeSortSerial(arr, left, mid);
  113.     mergeSortSerial(arr, mid + 1, right);
  114.     mergeSerial(arr, left, mid, right);
  115. }
  116.  
  117. // Merge function in Parallel
  118. void mergeParallel(vector<int>& arr, int left, int mid, int right) {
  119.     int n = mid - left + 1;
  120.     int m = right - mid;
  121.     vector<int> L(n), R(m);
  122. #pragma omp parallel for
  123.     for (int i = 0; i < n; ++i)
  124.         L[i] = arr[left + i];
  125. #pragma omp parallel for
  126.     for (int j = 0; j < m; ++j)
  127.         R[j] = arr[mid + 1 + j];
  128.     int i = 0, j = 0, k = left;
  129.     while (i < n && j < m) {
  130.         if (L[i] <= R[j]) {
  131.             arr[k] = L[i];
  132.             ++i;
  133.         }
  134.         else {
  135.             arr[k] = R[j];
  136.             ++j;
  137.         }
  138.         ++k;
  139.     }
  140.     while (i < n) {
  141.         arr[k] = L[i];
  142.         ++i;
  143.         ++k;
  144.     }
  145.     while (j < m) {
  146.         arr[k] = R[j];
  147.         ++j;
  148.         ++k;
  149.     }
  150. }
  151.  
  152. // Merge sort in parallel mode
  153. void mergeSortParallel(vector<int>& arr, int left, int right) {
  154.     if (left >= right) return;
  155.     int mid = left + (right - left) / 2;
  156. #pragma omp parallel sections
  157.     {
  158. #pragma omp section
  159.         mergeSortParallel(arr, left, mid);
  160. #pragma omp section
  161.         mergeSortParallel(arr, mid + 1, right);
  162.     }
  163.     mergeParallel(arr, left, mid, right);
  164. }
  165.  
  166. // Quick Sort partition in Serial
  167. int partitionSerial(vector<int>& arr, int low, int high) {
  168.     int pivot = arr[high];
  169.     int i = low - 1;
  170.     for (int j = low; j <= high - 1; ++j) {
  171.         if (arr[j] < pivot) {
  172.             ++i;
  173.             swap(arr[i], arr[j]);
  174.         }
  175.     }
  176.     swap(arr[i + 1], arr[high]);
  177.     return (i + 1);
  178. }
  179.  
  180. // Quick Sort in serial mode
  181. void quickSortSerial(vector<int>& arr, int low, int high) {
  182.     if (low < high) {
  183.         int mid = partitionSerial(arr, low, high);
  184.         quickSortSerial(arr, low, mid - 1);
  185.         quickSortSerial(arr, mid + 1, high);
  186.     }
  187. }
  188.  
  189. // Quick Sort partiton in Parallel
  190. int partitionParallel(vector<int>& arr, int low, int high) {
  191.     int pivot = arr[high];
  192.     int i = low - 1;
  193. #pragma omp parallel for
  194.     for (int j = low; j <= high - 1; ++j) {
  195.         if (arr[j] < pivot) {
  196. #pragma omp critical
  197.             {
  198.                 ++i;
  199.                 swap(arr[i], arr[j]);
  200.             }
  201.         }
  202.     }
  203.     swap(arr[i + 1], arr[high]);
  204.     return (i + 1);
  205. }
  206.  
  207. // Quick Sort in Parallel mode
  208. void quickSortParallel(vector<int>& arr, int low, int high) {
  209.     if (low < high) {
  210.         int mid = partitionParallel(arr, low, high);
  211. #pragma omp parallel sections
  212.         {
  213. #pragma omp section
  214.             quickSortParallel(arr, low, mid - 1);
  215. #pragma omp section
  216.             quickSortParallel(arr, mid + 1, high);
  217.         }
  218.     }
  219. }
  220.  
  221. int main() {
  222.     int length = 1000; // Length of the array
  223.     vector<int> array = randomArray(length);
  224.  
  225.     // Bubble sort execution time in serial
  226.     auto serialBubbleStartTime = high_resolution_clock::now();
  227.     bubbleSortSerial(array);
  228.     auto serialBubbleEndTime = high_resolution_clock::now();
  229.     double serialBubbleTime = duration_cast<milliseconds>(serialBubbleEndTime - serialBubbleStartTime).count() / 1000.0;
  230.  
  231.     // Insertion sort execution time in serial
  232.     auto serialInsertionStartTime = high_resolution_clock::now();
  233.     insertionSortSerial(array);
  234.     auto serialInsertionEndTime = high_resolution_clock::now();
  235.     double serialInsertionTime = duration_cast<milliseconds>(serialInsertionEndTime - serialInsertionStartTime).count() / 1000.0;
  236.  
  237.     // Merge sort execution time in serial
  238.     auto serialMergeStartTime = high_resolution_clock::now();
  239.     mergeSortSerial(array, 0, length - 1);
  240.     auto serialMergeEndTime = high_resolution_clock::now();
  241.     double serialMergeTime = duration_cast<milliseconds>(serialMergeEndTime - serialMergeStartTime).count() / 1000.0;
  242.  
  243.     // Quick sort execution time in serial
  244.     auto serialQuickStartTime = high_resolution_clock::now();
  245.     quickSortSerial(array, 0, length - 1);
  246.     auto serialQuickEndTime = high_resolution_clock::now();
  247.     double serialQuickTime = duration_cast<milliseconds>(serialQuickEndTime - serialQuickStartTime).count() / 1000.0;
  248.  
  249.     cout << "Serial time for Bubble Sort: " << serialBubbleTime << " seconds." << endl;
  250.     cout << "Serial time for Insertion Sort: " << serialInsertionTime << " seconds." << endl;
  251.     cout << "Serial time for Merge Sort: " << serialMergeTime << " seconds." << endl;
  252.     cout << "Serial time for Quick Sort: " << serialQuickTime << " seconds." << endl;
  253.  
  254.     // Parallel sorting using OpenMP
  255.     // Bubble sort execution time in parallel
  256.     auto parallelBubbleStartTime = high_resolution_clock::now();
  257.     bubbleSortParallel(array);
  258.     auto parallelBubbleEndTime = high_resolution_clock::now();
  259.     double parallelBubbleTime = duration_cast<milliseconds>(parallelBubbleEndTime - parallelBubbleStartTime).count() / 1000.0;
  260.  
  261.     // Insertion sort execution time in parallel
  262.     auto parallelInsertionStartTime = high_resolution_clock::now();
  263.     insertionSortParallel(array);
  264.     auto parallelInsertionEndTime = high_resolution_clock::now();
  265.     double parallelInsertionTime = duration_cast<milliseconds>(parallelInsertionEndTime - parallelInsertionStartTime).count() / 1000.0;
  266.  
  267.     // Merge sort execution time in parallel
  268.     auto parallelMergeStartTime = high_resolution_clock::now();
  269.     mergeSortParallel(array, 0, length - 1);
  270.     auto parallelMergeEndTime = high_resolution_clock::now();
  271.     double parallelMergeTime = duration_cast<milliseconds>(parallelMergeEndTime - parallelMergeStartTime).count() / 1000.0;
  272.  
  273.     // Quick sort execution time in parallel
  274.     auto parallelQuickStartTime = high_resolution_clock::now();
  275.     quickSortParallel(array, 0, length - 1);
  276.     auto parallelQuickEndTime = high_resolution_clock::now();
  277.     double parallelQuickTime = duration_cast<milliseconds>(parallelQuickEndTime - parallelQuickStartTime).count() / 1000.0;
  278.  
  279.     cout << "Parallel time for Bubble Sort: " << parallelBubbleTime << " seconds." << endl;
  280.     cout << "Parallel time for Insertion Sort: " << parallelInsertionTime << " seconds." << endl;
  281.     cout << "Parallel time for Merge Sort: " << parallelMergeTime << " seconds." << endl;
  282.     cout << "Parallel time for Quick Sort: " << parallelQuickTime << " seconds." << endl;
  283.  
  284.     return 0;
  285. }
  286.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Serial time for Bubble Sort: 0 seconds.
Serial time for Insertion Sort: 0 seconds.
Serial time for Merge Sort: 0 seconds.
Serial time for Quick Sort: 0 seconds.
Parallel time for Bubble Sort: 0 seconds.
Parallel time for Insertion Sort: 0 seconds.
Parallel time for Merge Sort: 0 seconds.
Parallel time for Quick Sort: 0 seconds.
https://ideone.com/dNnYSQ
language:
C++ (gcc 8.3)
created:
175 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!