BucketSortThreading.cpp

#include <iostream>
#include <vector>
#include <thread>
#include <chrono>
#include <algorithm>

using namespace std;
using namespace std::chrono;

int SIZE = 10;

void bucketSort(int arr[], int n) {
    // 1) Create n empty buckets
    vector<int>* bucket = new vector<int>[n];

    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }

    // 2) Put array elements in different buckets
    for (int i = 0; i < n; i++) {
        int bi = (n * arr[i]) / (maxVal + 1); // Index in bucket
        bucket[bi].push_back(arr[i]);
    }

    // 3) Sort individual buckets
    for (int i = 0; i < n; i++) {
        sort(bucket[i].begin(), bucket[i].end());
    }

    // 4) Concatenate all buckets into arr[]
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < bucket[i].size(); j++)
            arr[index++] = bucket[i][j];
}

void printArray(vector<int>& array);
void printArray(int *array, int sz);

void mergeArrays(int arr1[], int arr2[], int n1,
                 int n2, int arr3[]);


int main() {
    vector<int> a(SIZE);
    int* leftArray = (int *)malloc((SIZE/2+1) * sizeof(int));
    int* rightArray = (int *)malloc((SIZE/2+1) * sizeof(int));

    for (int m = 0; m < SIZE; m++) {
        a[m] = rand()%10;
    }

    for (int i = 0; i < SIZE/2; ++i) leftArray[i] = a[i];
    for (int i = 0, j = SIZE/2; i < SIZE/2; ++i, j++) {
        rightArray[i] = a[j];
    }

    thread t1 (bucketSort, leftArray, SIZE/2);
    thread t2 (bucketSort, rightArray, SIZE/2);

    t1.join();
    t2.join();

    int sortedArray[SIZE];
    mergeArrays(leftArray, rightArray, SIZE/2, SIZE/2, sortedArray);

//    printArray(leftArray, SIZE/2);
//    printArray(rightArray, SIZE/2);


    printArray(a);
    printArray(sortedArray, SIZE);
    cout << endl;
    return 0;
}

void printArray(vector<int>& array){
    for (int i = 0; i < SIZE; ++i) cout << array[i] << ' ';
    cout << endl;
}

void printArray(int *array, int sz){
    for (int i = 0; i < sz; ++i) cout << array[i] << ' ';
    cout << endl;
}

void mergeArrays(int arr1[], int arr2[], int n1,
                 int n2, int arr3[]) {
    int i = 0, j = 0, k = 0;
    while (i<n1 && j <n2) {
        if (arr1[i] < arr2[j])
            arr3[k++] = arr1[i++];
        else
            arr3[k++] = arr2[j++];
    }

    while (i < n1)
        arr3[k++] = arr1[i++];

    while (j < n2)
        arr3[k++] = arr2[j++];
}