fork download
copy 
  1. #include <omp.h>  //omenmp library for parallel processing
  2. #include <stdlib.h> // Standard library for memory allocation and random number generation.
  3. #include <array>
  4. #include <chrono> // for woring with time, clocks and timers
  5. #include <functional> // predefined functions for working with functions in a more flexible and generic way
  6. #include <iostream>
  7. #include <string>
  8. #include <vector>
  9.  
  10. using std::chrono::duration_cast; // converting between different durations (eg. milisecs to secs)
  11. using std::chrono::high_resolution_clock; // used for high resolution timing measurements
  12. using std::chrono::milliseconds; // representing a period of time in milliseconds.
  13. using namespace std;
  14.  
  15. void s_bubble(int *, int); // sequential buble-sort function declaration
  16. void p_bubble(int *, int); // parallel buble-sort function declaration
  17. void swap(int &, int &);
  18.  
  19. // sequential bubble-sort
  20. void s_bubble(int *a, int n) {
  21.     for (int i = 0; i < n; i++) {
  22.         int first = i % 2;
  23.         for (int j = first; j < n - 1; j += 2) {
  24.             if (a[j] > a[j + 1]) {
  25.                 swap(a[j], a[j + 1]);
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. // parallel bubble-sort
  32. void p_bubble(int *a, int n) {
  33.     for (int i = 0; i < n; i++) {
  34.         int first = i % 2;
  35. #pragma omp parallel for shared(a, first) num_threads(16)
  36.         for (int j = first; j < n - 1; j += 2) {
  37.             if (a[j] > a[j + 1]) {
  38.                 swap(a[j], a[j + 1]);
  39.             }
  40.         }
  41.     }
  42. }
  43.  
  44. // swapping two numbers
  45. void swap(int &a, int &b) {
  46.     int test;
  47.     test = a;
  48.     a = b;
  49.     b = test;
  50. }
  51.  
  52. // measures the execution time of a given function using traverse_fn
  53. std::string bench_traverse(std::function<void()> traverse_fn) {
  54.     auto start = high_resolution_clock::now();
  55.     traverse_fn();
  56.     auto stop = high_resolution_clock::now();
  57.  
  58.     // Subtract stop and start timepoints and cast it to required unit.
  59.     // Predefined units are nanoseconds, microseconds, milliseconds, seconds,
  60.     // minutes, hours. Use duration_cast() function.
  61.     auto duration = duration_cast<milliseconds>(stop - start);
  62.  
  63.     // To get the value of duration use the count() member function on the
  64.     // duration object
  65.     return std::to_string(duration.count());
  66. }
  67.  
  68. // argc: argument count(represents the number of command-line arguments passed to the program)
  69. // **argv: representing the command-line arguments themselves.
  70. int main(int argc, const char **argv) {
  71.     int n = 1000; 
  72.     int rand_max = 100000;
  73.     int *a;
  74.  
  75.     // cout<<"\n Enter n "<<endl;
  76.     // cin>>n;
  77.     // cout<<"\n Enter rand_max"<<endl;
  78.     // cin>>rand_max;
  79.  
  80.     // n = stoi(argv[1]); // first command line arguument (array length)
  81.     // rand_max = stoi(argv[2]); // second command line argument (maximum random value)
  82.     a = new int[n]; // dynamic array oof size n
  83.  
  84.     //  fills the array a with random integer values between 0 and rand_max.
  85.     for (int i = 0; i < n; i++) {
  86.         a[i] = rand() % rand_max;
  87.     }
  88.  
  89.     // Another array b is dynamically allocated and initialized with the same contents as array a.
  90.     int *b = new int[n];
  91.     copy(a, a + n, b);
  92.  
  93.     // Displaying message
  94.     cout << "Generated random array of length " << n << " with elements between 0 to " << rand_max
  95.          << "\n\n";
  96.  
  97.  
  98.     // performs a sequential bubble sort on array a using the s_bubble function and measures the time it takes using bench_traverse.
  99.     std::cout << "Sequential Bubble sort: " << bench_traverse([&] { s_bubble(a, n); }) << "ms\n";
  100.     // printing sorted array
  101.     cout << "Sorted array is =>\n";
  102.     for (int i = 0; i < n; i++) {
  103.         cout << a[i] << ", ";
  104.     }
  105.     cout << "\n\n";
  106.  
  107.     // sets the number of threads to 16 for OpenMP parallelization
  108.     // omp_set_num_threads(16);
  109.  
  110.     // performs a parallel bubble sort on array b using the p_bubble function, measuring the time with bench_traverse
  111.     std::cout << "Parallel (16) Bubble sort: " << bench_traverse([&] { p_bubble(b, n); }) << "ms\n";
  112.     // printing sorted array
  113.     cout << "Sorted array is =>\n";
  114.     for (int i = 0; i < n; i++) {
  115.         cout << b[i] << ", ";
  116.     }
  117.     return 0;
  118. }
  119.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generated random array of length 1000 with elements between 0 to 100000

Sequential Bubble sort: 0ms
Sorted array is =>
81, 237, 346, 545, 569, 606, 657, 681, 723, 925, 973, 1039, 1052, 1063, 1255, 1360, 1474, 1839, 1947, 1961, 1962, 2021, 2215, 2245, 2254, 2305, 2336, 2362, 2422, 2567, 2647, 2651, 2726, 2747, 2829, 2900, 2904, 2954, 3033, 3074, 3135, 3177, 3190, 3348, 3465, 3493, 3526, 3682, 3729, 3881, 4234, 4289, 4292, 4310, 4339, 4346, 4567, 4789, 4794, 4916, 5000, 5057, 5153, 5211, 5236, 5363, 5385, 5403, 5624, 5732, 5771, 5989, 6042, 6219, 6355, 6367, 6403, 6445, 6582, 6640, 6710, 6725, 6732, 6862, 6887, 6996, 7205, 7398, 7556, 7669, 7672, 7722, 7971, 8117, 8235, 8282, 8324, 8538, 8542, 8581, 8860, 8872, 8902, 8933, 9016, 9097, 9117, 9188, 9211, 9365, 9441, 9485, 9503, 9610, 9859, 9933, 10012, 10097, 10197, 10253, 10294, 10498, 10537, 10563, 10699, 10873, 10991, 11017, 11127, 11131, 11305, 11340, 11388, 11574, 11705, 11776, 11783, 11898, 11899, 11972, 12183, 12297, 12350, 12399, 12497, 12902, 12924, 13073, 13173, 13202, 13258, 13563, 13750, 13773, 13784, 13810, 13926, 13929, 13970, 13996, 14030, 14412, 14500, 14613, 14639, 14653, 14677, 14769, 14904, 15334, 15350, 15434, 15667, 15720, 15775, 15797, 16124, 16127, 16437, 16466, 16539, 16649, 16931, 16949, 17276, 17445, 17462, 17505, 17567, 17647, 17721, 17955, 17988, 18004, 18149, 18157, 18184, 18189, 18418, 18456, 18593, 18606, 18627, 18657, 18776, 18808, 18944, 18996, 19080, 19125, 19218, 19301, 19379, 19529, 19582, 19593, 19756, 19805, 19847, 19934, 20059, 20090, 20127, 20483, 20504, 20709, 20853, 20925, 21120, 21244, 21269, 21308, 21396, 21530, 21648, 21703, 21729, 21801, 21860, 21993, 22071, 22090, 22197, 22227, 22325, 22404, 22532, 22535, 22573, 22604, 22842, 22846, 22862, 22954, 23058, 23205, 23311, 23382, 23428, 23506, 23618, 23875, 23943, 24030, 24176, 24286, 24566, 24914, 25171, 25210, 25218, 25433, 25578, 25661, 25849, 25857, 26057, 26087, 26272, 26304, 26309, 26312, 26340, 26505, 26607, 26621, 26651, 26652, 26717, 26808, 26815, 26924, 27088, 27284, 27321, 27335, 27684, 27814, 27828, 27955, 28023, 28067, 28202, 28205, 28398, 28444, 28458, 28577, 28624, 28794, 28804, 28946, 28993, 29150, 29204, 29320, 29689, 29904, 30019, 30126, 30297, 30443, 30639, 30690, 30857, 30886, 31011, 31233, 31326, 31491, 31536, 31626, 32002, 32036, 32133, 32172, 32231, 32290, 32460, 32871, 32919, 33002, 33069, 33074, 33149, 33333, 33367, 33378, 33417, 33452, 33459, 33483, 33518, 33589, 33681, 33890, 34022, 34047, 34225, 34471, 34481, 34713, 34945, 34994, 35021, 35128, 35189, 35217, 35325, 35379, 35568, 35710, 35821, 35928, 35990, 36029, 36159, 36226, 36327, 36429, 36503, 36610, 36784, 36836, 36840, 36873, 36915, 36987, 37457, 37525, 37732, 37764, 38046, 38082, 38097, 38283, 38335, 38377, 38701, 38722, 38839, 39006, 39021, 39036, 39214, 39299, 39390, 39507, 39529, 39668, 39811, 39848, 39862, 39932, 40049, 40084, 40528, 40713, 40743, 40795, 40865, 41081, 41222, 41312, 41421, 41500, 41723, 41805, 41873, 41888, 41892, 42062, 42587, 42590, 42618, 42698, 43181, 43324, 43376, 43437, 43555, 43768, 43921, 44043, 44234, 44266, 44500, 44599, 44729, 44818, 44822, 44878, 44918, 44919, 45053, 45082, 45196, 45486, 45550, 45630, 45691, 45729, 45791, 45830, 45884, 45894, 45975, 46081, 46139, 46228, 46491, 46619, 47084, 47178, 47255, 47283, 47386, 47468, 47625, 47641, 47643, 47686, 47739, 47793, 47796, 48036, 48094, 48142, 48365, 48412, 48518, 48522, 48566, 48626, 48720, 48829, 48899, 49122, 49157, 49250, 49291, 49299, 49314, 49614, 49676, 49797, 49908, 49958, 50253, 50262, 50270, 50543, 50551, 50573, 50774, 50846, 50907, 51136, 51432, 51434, 51476, 51528, 51659, 51746, 52040, 52274, 52298, 52433, 52506, 52528, 52551, 52715, 52805, 52926, 52959, 52996, 53144, 53195, 53275, 53414, 53516, 53541, 53714, 53826, 53865, 53895, 53959, 54010, 54081, 54098, 54116, 54154, 54259, 54340, 54538, 54552, 54586, 54603, 55081, 55115, 55199, 55306, 55340, 55422, 55542, 55590, 55629, 55736, 55763, 55805, 55936, 55939, 56042, 56190, 56429, 56552, 56620, 56682, 56728, 56851, 56856, 56970, 57034, 57199, 57522, 57753, 58025, 58031, 58109, 58270, 58270, 58390, 58440, 58660, 58699, 58955, 58969, 59211, 59231, 59355, 59415, 59426, 59470, 59479, 59708, 59956, 59999, 60008, 60028, 60049, 60099, 60235, 60269, 60280, 60289, 60336, 60358, 60378, 60379, 60492, 60756, 60910, 60997, 61041, 61152, 61237, 61313, 61393, 61682, 61796, 61886, 62009, 62504, 62600, 62754, 62806, 62949, 62951, 63291, 63368, 63827, 63858, 63920, 63950, 63981, 64285, 64370, 64443, 64524, 64683, 64819, 65084, 65100, 65123, 65193, 65404, 65421, 65782, 65818, 65984, 66127, 66143, 66189, 66249, 66328, 66342, 66342, 66413, 66601, 66748, 66761, 66950, 66996, 67057, 67269, 67372, 67587, 67605, 67621, 67637, 67637, 67770, 67818, 67857, 67868, 67917, 68139, 68363, 68690, 68825, 68850, 68858, 68977, 68980, 69086, 69179, 69633, 69786, 69841, 69911, 69917, 70072, 70124, 70163, 70337, 70347, 70460, 70478, 70492, 70688, 70888, 71043, 71087, 71137, 71155, 71232, 71338, 71559, 71692, 72231, 72260, 72261, 72353, 72379, 72555, 72641, 72661, 72757, 72813, 72890, 73059, 73109, 73168, 73303, 73317, 73416, 73622, 73730, 73743, 73788, 73793, 73813, 73850, 73940, 74067, 74232, 74570, 74580, 74762, 75011, 75055, 75105, 75198, 75223, 75266, 75321, 75407, 75569, 75579, 75640, 75776, 75856, 76091, 76121, 76229, 76335, 76348, 76376, 76590, 76787, 76882, 76965, 76982, 77017, 77084, 77217, 77373, 77375, 77560, 77685, 77856, 77888, 78042, 78050, 78130, 78179, 78206, 78224, 78611, 78736, 79107, 79207, 79262, 79292, 79296, 79444, 79497, 79567, 79802, 80154, 80226, 80308, 80524, 80540, 80570, 80595, 80928, 80952, 80967, 81095, 81486, 81494, 81776, 81936, 82030, 82134, 82195, 82338, 83303, 83426, 83898, 84172, 84278, 84421, 84812, 84850, 84857, 84930, 85054, 85147, 85238, 85273, 85386, 85404, 85644, 85795, 86059, 86248, 86593, 86708, 86715, 86763, 86990, 87090, 87131, 87190, 87343, 87483, 87516, 87560, 87677, 87743, 87764, 87770, 87981, 87982, 88027, 88209, 88228, 88355, 88464, 88574, 88711, 88777, 88819, 88954, 89114, 89126, 89159, 89172, 89224, 89368, 89383, 89412, 89435, 89438, 89528, 89618, 89672, 89683, 89685, 89744, 89772, 90000, 90027, 90032, 90071, 90179, 90181, 90358, 90360, 90364, 90368, 90415, 90417, 90428, 90596, 90613, 90675, 90783, 90868, 90930, 90964, 91100, 91171, 91281, 91298, 91309, 91521, 92122, 92292, 92350, 92379, 92393, 92622, 92685, 92735, 92754, 92777, 92921, 93093, 93368, 93451, 93499, 93512, 93529, 93584, 93614, 93740, 94018, 94324, 94395, 94427, 94428, 94583, 94892, 94977, 94984, 95021, 95060, 95151, 95343, 95367, 95368, 95425, 95436, 95499, 95528, 95746, 95788, 95820, 95994, 96157, 96431, 96532, 96658, 96776, 96892, 96963, 97278, 97281, 97301, 97314, 97369, 97467, 97487, 97488, 97490, 97525, 97539, 97697, 97713, 97763, 98167, 98285, 98315, 98338, 98382, 98490, 98506, 98537, 98571, 98586, 98814, 98898, 98927, 98976, 98987, 99051, 99134, 99170, 99181, 99228, 99336, 99631, 99708, 99754, 99759, 99904, 99932, 

Parallel (16) Bubble sort: 0ms
Sorted array is =>
81, 237, 346, 545, 569, 606, 657, 681, 723, 925, 973, 1039, 1052, 1063, 1255, 1360, 1474, 1839, 1947, 1961, 1962, 2021, 2215, 2245, 2254, 2305, 2336, 2362, 2422, 2567, 2647, 2651, 2726, 2747, 2829, 2900, 2904, 2954, 3033, 3074, 3135, 3177, 3190, 3348, 3465, 3493, 3526, 3682, 3729, 3881, 4234, 4289, 4292, 4310, 4339, 4346, 4567, 4789, 4794, 4916, 5000, 5057, 5153, 5211, 5236, 5363, 5385, 5403, 5624, 5732, 5771, 5989, 6042, 6219, 6355, 6367, 6403, 6445, 6582, 6640, 6710, 6725, 6732, 6862, 6887, 6996, 7205, 7398, 7556, 7669, 7672, 7722, 7971, 8117, 8235, 8282, 8324, 8538, 8542, 8581, 8860, 8872, 8902, 8933, 9016, 9097, 9117, 9188, 9211, 9365, 9441, 9485, 9503, 9610, 9859, 9933, 10012, 10097, 10197, 10253, 10294, 10498, 10537, 10563, 10699, 10873, 10991, 11017, 11127, 11131, 11305, 11340, 11388, 11574, 11705, 11776, 11783, 11898, 11899, 11972, 12183, 12297, 12350, 12399, 12497, 12902, 12924, 13073, 13173, 13202, 13258, 13563, 13750, 13773, 13784, 13810, 13926, 13929, 13970, 13996, 14030, 14412, 14500, 14613, 14639, 14653, 14677, 14769, 14904, 15334, 15350, 15434, 15667, 15720, 15775, 15797, 16124, 16127, 16437, 16466, 16539, 16649, 16931, 16949, 17276, 17445, 17462, 17505, 17567, 17647, 17721, 17955, 17988, 18004, 18149, 18157, 18184, 18189, 18418, 18456, 18593, 18606, 18627, 18657, 18776, 18808, 18944, 18996, 19080, 19125, 19218, 19301, 19379, 19529, 19582, 19593, 19756, 19805, 19847, 19934, 20059, 20090, 20127, 20483, 20504, 20709, 20853, 20925, 21120, 21244, 21269, 21308, 21396, 21530, 21648, 21703, 21729, 21801, 21860, 21993, 22071, 22090, 22197, 22227, 22325, 22404, 22532, 22535, 22573, 22604, 22842, 22846, 22862, 22954, 23058, 23205, 23311, 23382, 23428, 23506, 23618, 23875, 23943, 24030, 24176, 24286, 24566, 24914, 25171, 25210, 25218, 25433, 25578, 25661, 25849, 25857, 26057, 26087, 26272, 26304, 26309, 26312, 26340, 26505, 26607, 26621, 26651, 26652, 26717, 26808, 26815, 26924, 27088, 27284, 27321, 27335, 27684, 27814, 27828, 27955, 28023, 28067, 28202, 28205, 28398, 28444, 28458, 28577, 28624, 28794, 28804, 28946, 28993, 29150, 29204, 29320, 29689, 29904, 30019, 30126, 30297, 30443, 30639, 30690, 30857, 30886, 31011, 31233, 31326, 31491, 31536, 31626, 32002, 32036, 32133, 32172, 32231, 32290, 32460, 32871, 32919, 33002, 33069, 33074, 33149, 33333, 33367, 33378, 33417, 33452, 33459, 33483, 33518, 33589, 33681, 33890, 34022, 34047, 34225, 34471, 34481, 34713, 34945, 34994, 35021, 35128, 35189, 35217, 35325, 35379, 35568, 35710, 35821, 35928, 35990, 36029, 36159, 36226, 36327, 36429, 36503, 36610, 36784, 36836, 36840, 36873, 36915, 36987, 37457, 37525, 37732, 37764, 38046, 38082, 38097, 38283, 38335, 38377, 38701, 38722, 38839, 39006, 39021, 39036, 39214, 39299, 39390, 39507, 39529, 39668, 39811, 39848, 39862, 39932, 40049, 40084, 40528, 40713, 40743, 40795, 40865, 41081, 41222, 41312, 41421, 41500, 41723, 41805, 41873, 41888, 41892, 42062, 42587, 42590, 42618, 42698, 43181, 43324, 43376, 43437, 43555, 43768, 43921, 44043, 44234, 44266, 44500, 44599, 44729, 44818, 44822, 44878, 44918, 44919, 45053, 45082, 45196, 45486, 45550, 45630, 45691, 45729, 45791, 45830, 45884, 45894, 45975, 46081, 46139, 46228, 46491, 46619, 47084, 47178, 47255, 47283, 47386, 47468, 47625, 47641, 47643, 47686, 47739, 47793, 47796, 48036, 48094, 48142, 48365, 48412, 48518, 48522, 48566, 48626, 48720, 48829, 48899, 49122, 49157, 49250, 49291, 49299, 49314, 49614, 49676, 49797, 49908, 49958, 50253, 50262, 50270, 50543, 50551, 50573, 50774, 50846, 50907, 51136, 51432, 51434, 51476, 51528, 51659, 51746, 52040, 52274, 52298, 52433, 52506, 52528, 52551, 52715, 52805, 52926, 52959, 52996, 53144, 53195, 53275, 53414, 53516, 53541, 53714, 53826, 53865, 53895, 53959, 54010, 54081, 54098, 54116, 54154, 54259, 54340, 54538, 54552, 54586, 54603, 55081, 55115, 55199, 55306, 55340, 55422, 55542, 55590, 55629, 55736, 55763, 55805, 55936, 55939, 56042, 56190, 56429, 56552, 56620, 56682, 56728, 56851, 56856, 56970, 57034, 57199, 57522, 57753, 58025, 58031, 58109, 58270, 58270, 58390, 58440, 58660, 58699, 58955, 58969, 59211, 59231, 59355, 59415, 59426, 59470, 59479, 59708, 59956, 59999, 60008, 60028, 60049, 60099, 60235, 60269, 60280, 60289, 60336, 60358, 60378, 60379, 60492, 60756, 60910, 60997, 61041, 61152, 61237, 61313, 61393, 61682, 61796, 61886, 62009, 62504, 62600, 62754, 62806, 62949, 62951, 63291, 63368, 63827, 63858, 63920, 63950, 63981, 64285, 64370, 64443, 64524, 64683, 64819, 65084, 65100, 65123, 65193, 65404, 65421, 65782, 65818, 65984, 66127, 66143, 66189, 66249, 66328, 66342, 66342, 66413, 66601, 66748, 66761, 66950, 66996, 67057, 67269, 67372, 67587, 67605, 67621, 67637, 67637, 67770, 67818, 67857, 67868, 67917, 68139, 68363, 68690, 68825, 68850, 68858, 68977, 68980, 69086, 69179, 69633, 69786, 69841, 69911, 69917, 70072, 70124, 70163, 70337, 70347, 70460, 70478, 70492, 70688, 70888, 71043, 71087, 71137, 71155, 71232, 71338, 71559, 71692, 72231, 72260, 72261, 72353, 72379, 72555, 72641, 72661, 72757, 72813, 72890, 73059, 73109, 73168, 73303, 73317, 73416, 73622, 73730, 73743, 73788, 73793, 73813, 73850, 73940, 74067, 74232, 74570, 74580, 74762, 75011, 75055, 75105, 75198, 75223, 75266, 75321, 75407, 75569, 75579, 75640, 75776, 75856, 76091, 76121, 76229, 76335, 76348, 76376, 76590, 76787, 76882, 76965, 76982, 77017, 77084, 77217, 77373, 77375, 77560, 77685, 77856, 77888, 78042, 78050, 78130, 78179, 78206, 78224, 78611, 78736, 79107, 79207, 79262, 79292, 79296, 79444, 79497, 79567, 79802, 80154, 80226, 80308, 80524, 80540, 80570, 80595, 80928, 80952, 80967, 81095, 81486, 81494, 81776, 81936, 82030, 82134, 82195, 82338, 83303, 83426, 83898, 84172, 84278, 84421, 84812, 84850, 84857, 84930, 85054, 85147, 85238, 85273, 85386, 85404, 85644, 85795, 86059, 86248, 86593, 86708, 86715, 86763, 86990, 87090, 87131, 87190, 87343, 87483, 87516, 87560, 87677, 87743, 87764, 87770, 87981, 87982, 88027, 88209, 88228, 88355, 88464, 88574, 88711, 88777, 88819, 88954, 89114, 89126, 89159, 89172, 89224, 89368, 89383, 89412, 89435, 89438, 89528, 89618, 89672, 89683, 89685, 89744, 89772, 90000, 90027, 90032, 90071, 90179, 90181, 90358, 90360, 90364, 90368, 90415, 90417, 90428, 90596, 90613, 90675, 90783, 90868, 90930, 90964, 91100, 91171, 91281, 91298, 91309, 91521, 92122, 92292, 92350, 92379, 92393, 92622, 92685, 92735, 92754, 92777, 92921, 93093, 93368, 93451, 93499, 93512, 93529, 93584, 93614, 93740, 94018, 94324, 94395, 94427, 94428, 94583, 94892, 94977, 94984, 95021, 95060, 95151, 95343, 95367, 95368, 95425, 95436, 95499, 95528, 95746, 95788, 95820, 95994, 96157, 96431, 96532, 96658, 96776, 96892, 96963, 97278, 97281, 97301, 97314, 97369, 97467, 97487, 97488, 97490, 97525, 97539, 97697, 97713, 97763, 98167, 98285, 98315, 98338, 98382, 98490, 98506, 98537, 98571, 98586, 98814, 98898, 98927, 98976, 98987, 99051, 99134, 99170, 99181, 99228, 99336, 99631, 99708, 99754, 99759, 99904, 99932,
https://ideone.com/cTZia4
language:
C++14 (gcc 8.3)
created:
10 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!