fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <thread>
  4. #include <mutex>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. mutex mtx; // Mutex to synchronize access to shared histogram
  10.  
  11. // Function to generate a histogram for a portion of the array
  12. void generateHistogram(const vector<int>& arr, int start, int end, vector<int>& histogram, int minVal) {
  13.     for (int i = start; i < end; ++i) {
  14.         int index = arr[i] - minVal; // Find the position in histogram
  15.         mtx.lock();
  16.         histogram[index]++; // Update histogram safely
  17.         mtx.unlock();
  18.     }
  19.  
  20.     // Display the thread's work
  21.     cout << "Thread " << this_thread::get_id() << " processed indices [" << start << ", " << end - 1 << "]\n";
  22. }
  23.  
  24. // Function to perform distributed histogram sort
  25. void distributedHistogramSort(vector<int>& arr, int numThreads) {
  26.     // Find the range of elements in the array (min and max)
  27.     int minElem = *min_element(arr.begin(), arr.end());
  28.     int maxElem = *max_element(arr.begin(), arr.end());
  29.  
  30.     int range = maxElem - minElem + 1; // Range of values in the array
  31.     vector<int> histogram(range, 0);   // Histogram to count occurrences of each element
  32.  
  33.     // Determine the chunk size for each thread
  34.     int chunkSize = arr.size() / numThreads;
  35.     vector<thread> threads;
  36.  
  37.     // Create threads to generate histograms in parallel
  38.     for (int i = 0; i < numThreads; ++i) {
  39.         int start = i * chunkSize;
  40.         int end = (i == numThreads - 1) ? arr.size() : (i + 1) * chunkSize;
  41.  
  42.         // Each thread generates a histogram for a portion of the array
  43.         threads.push_back(thread(generateHistogram, ref(arr), start, end, ref(histogram), minElem));
  44.     }
  45.  
  46.     // Wait for all threads to finish
  47.     for (auto& t : threads) {
  48.         t.join();
  49.     }
  50.  
  51.     // Reconstruct the sorted array based on the histogram
  52.     vector<int> sortedArr;
  53.     for (int i = 0; i < range; ++i) {
  54.         sortedArr.insert(sortedArr.end(), histogram[i], i + minElem);
  55.     }
  56.  
  57.     // Copy the sorted data back into the original array
  58.     arr = sortedArr;
  59. }
  60.  
  61. int main() {
  62.     // Example unsorted array
  63.     vector<int> arr = {12, 3, 5, 7, 19, 2, 8, 13, 4, 15, 6, 11, 10};
  64.  
  65.     int numThreads = 4; // Number of threads to use for parallelism
  66.  
  67.     cout << "Unsorted Array:\n";
  68.     for (int num : arr) {
  69.         cout << num << " ";
  70.     }
  71.     cout << endl;
  72.  
  73.     // Perform distributed histogram sort
  74.     distributedHistogramSort(arr, numThreads);
  75.  
  76.     cout << "Sorted Array:\n";
  77.     for (int num : arr) {
  78.         cout << num << " ";
  79.     }
  80.     cout << endl;
  81.  
  82.     return 0;
  83. }
  84.  
  85.  
  86.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Unsorted Array:
12 3 5 7 19 2 8 13 4 15 6 11 10 
Thread 22701416154880 processed indices [9, 12]
Thread 22701418256128 processed indices [6, 8]
Thread 22701420357376 processed indices [3, 5]
Thread 22701422458624 processed indices [0, 2]
Sorted Array:
2 3 4 5 6 7 8 10 11 12 13 15 19
https://ideone.com/vCKiSD
language:
C++ (gcc 8.3)
created:
9 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!