ZidekThreads

// Thready2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <random>
#include <time.h>
#include <thread>

using std::cout;
using std::endl;

#define TYPE int
#define LENGTH 100000
#define COUNT 100

std::random_device dev;     // rd
std::mt19937 rng(dev());    // eng


// class for one part of task
class TaskPart
{
public:
    int m_id;                       // user thread identification
    int m_from, m_length, m_to;     // data range
    TYPE* m_data;                   // array
    TYPE m_max;                     // result

    TaskPart() {}

    TaskPart(int t_myid, int t_from, int t_length, TYPE* t_data) :
        m_id(t_myid), m_from(t_from), m_length(t_length), m_to(t_from + t_length), m_data(t_data) {}

    void generate_values() {
        std::uniform_real_distribution<> distr(0, LENGTH); // define the range
        for (int i = m_from; i < m_from + m_length; i++)
            m_data[i] = distr(rng);
    }

    void print_all() {
        for (int i = m_from; i < m_from + m_length; i++)
            cout << m_data[i] << ' ';
            cout << endl;
    }
    void bubbleSort() {
        for (int i = m_from; i < m_from + m_length; i++) {
            // Last i elements are already in place
            for (int j = 0; j < m_from + m_length - i; j++)
                if (m_data[j] < m_data[j + 1]) {
                    TYPE temp = m_data[j];
                    m_data[j] = m_data[j + 1];
                    m_data[j + 1] = temp;
                }
        }
    }

    void insertionSort() {
        long long i, j;
        TYPE key;
        for (i = 1 + m_from; i < m_from + m_length; i++) {
            key = m_data[i];
            j = i - 1;
            while (j >= 0 && m_data[j] < key) {
                m_data[j + 1] = m_data[j];
                j = j - 1;
            }
            m_data[j + 1] = key;
        }
    }

    void selectionSort() {
        long long i, j, min_idx;
        for (i = m_from; i < m_from + m_length - 1; i++) {
            min_idx = i;
            for (j = i + 1; j < m_from + m_length; j++)
                if (m_data[j] > m_data[min_idx])
                    min_idx = j;

            TYPE temp = m_data[i];
            m_data[i] = m_data[min_idx];
            m_data[min_idx] = temp;
        }
    }

};

void print(TYPE* arr, long from, long to) {
    std::cout << "\n";
    for (int i = from; i < to; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

void ParallelGenerator(TYPE* arr, long length, int threadCount) {
    //cout << "Running generating on " << threadCount << " threads." << std::endl;
    auto startTime = std::chrono::system_clock::now();

    std::thread* threads = new std::thread[threadCount];
    TaskPart* parts = new TaskPart[threadCount];

    int partLength = length / threadCount;

    for (int j = 0; j < threadCount; j++) {
        if (j < (threadCount - 1))
            parts[j] = TaskPart(j, (partLength * j), partLength, arr);
        else
            parts[j] = TaskPart(j, (partLength * j), partLength + (length % threadCount), arr); // add the remaining fields

        threads[j] = std::thread(&TaskPart::generate_values, parts[j]);
    }

    for (int j = 0; j < threadCount; j++) {
        threads[j].join();
    }

    delete[] threads;
    delete[] parts;

    auto endTime = std::chrono::system_clock::now();
    long dur = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
    std::cout << "Iteration done. (" << dur << " ms)" << std::endl << std::endl;
}

// zatial len selection funguje dobre
void ParallelSort(TYPE* arr, long length, int threadCount) {
    std::cout << "Running selection sort on " << threadCount << " threads." << std::endl;
    auto startTime = std::chrono::system_clock::now();

    std::thread* threads = new std::thread[threadCount];
    TaskPart* parts = new TaskPart[threadCount];

    int partLength = length / threadCount;

    for (int j = 0; j < threadCount; j++) {
        if (j < (threadCount - 1))
            parts[j] = TaskPart(j, (partLength * j), partLength, arr);
        else
            parts[j] = TaskPart(j, (partLength * j), partLength + (length % threadCount), arr); // add the remaining fields
        //std::cout << "Generating thread " << j << ", sorting from index " << parts[j].m_from << " to " << parts[j].m_length + parts[j].m_from-1 << std::endl;
        threads[j] = std::thread(&TaskPart::selectionSort, parts[j]);
    }

    for (int j = 0; j < threadCount; j++) {
        threads[j].join();
    }
    delete[] threads;
    delete[] parts;

    auto endTime = std::chrono::system_clock::now();
    long dur = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
    std::cout << "Iteration done. (" << dur << " ms)" << std::endl << std::endl;

}

void ArraysMerge(TYPE*& l_my_array, TYPE*& buffer, long start, long firstpartsize, long secondpartsize, long threads) { //DEPRECATED
        //auto startTime = std::chrono::system_clock::now();

    int secondstart = firstpartsize + start;


    int i = start, j = secondstart, k = start;

    // Traverse both array
    while (i < start + firstpartsize && j < secondstart + secondpartsize)
    {
        // Check if current element of first
        // array is smaller than current element
        // of second array. If yes, store first
        // array element and increment first array
        // index. Otherwise do same with second array
        if (l_my_array[i] > l_my_array[j])
            buffer[k++] = l_my_array[i++];
        else
            buffer[k++] = l_my_array[j++];
    }

    // Store remaining elements of first array
    while (i < start + firstpartsize)
        buffer[k++] = l_my_array[i++];

    // Store remaining elements of second array
    while (j < secondstart + secondpartsize)
        buffer[k++] = l_my_array[j++];
    //print(buffer, start, end);
    //delete l_my_array;
    for (int i = start; i < start + firstpartsize + secondpartsize; i++)
        l_my_array[i] = buffer[i];
    //l_my_sorted_array = nullptr;

    //auto endTime = std::chrono::system_clock::now();
    //long dur = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
    //std::cout << "Iteration done. (" << dur << " ms)" << std::endl << std::endl;
}

void bigMerge(TYPE*& l_my_array, long length, int threads) { //DEPRECATED
    std::cout << "Running merging " << threads << " arrays." << std::endl;
    auto startTime = std::chrono::system_clock::now();
    TYPE* buffer = new TYPE[length];
    int partLength = length / threads;
    for (int i = 0; i < partLength; i++)
    {
        buffer[i] = l_my_array[i];
    }
    for (int i = partLength; i < length - partLength + 1; i += partLength)
    {
        int from = i;
        int to = i + partLength;
        if (length - to < partLength)
            to = length;

        ArraysMerge(l_my_array, buffer, 0, i, to - from, 2);
    }

    auto endTime = std::chrono::system_clock::now();
    long dur = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
    std::cout << "Iteration done. (" << dur << " ms)" << std::endl << std::endl;
}

void mergeAll(TYPE*& arr, long length, int threadCount) {
    std::cout << "Running merging " << threadCount << " arrays." << std::endl;
    auto startTime = std::chrono::system_clock::now();
    TYPE* out = new TYPE[length];
    TaskPart* parts = new TaskPart[threadCount];

    int partLength = length / threadCount;

    for (int j = 0; j < threadCount; j++) {
        if (j < (threadCount - 1))
            parts[j] = TaskPart(j, (partLength * j), partLength, arr);
        else
            parts[j] = TaskPart(j, (partLength * j), partLength + (length % threadCount), arr); // add the remaining fields
    }

    unsigned j = 0;
    unsigned flag = 0;
    while (j < length)
    {
        TYPE min = INT64_MIN;
        for (unsigned i = 0; i < threadCount; i++)
        {
            if (arr[parts[i].m_from] > min&& parts[i].m_from < parts[i].m_to)
            {
                min = arr[parts[i].m_from];
                flag = i;
            }
        }
        out[j] = min;
        parts[flag].m_from += 1;
        j++;
    }
    delete arr;
    arr = out;
    auto endTime = std::chrono::system_clock::now();
    long dur = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
    std::cout << "Iteration done. (" << dur << " ms)" << std::endl << std::endl;
}

bool validateSortedArray(TYPE* l_my_array, long l_my_length) {
    for (int i = 0; i < l_my_length - 1; i++)
    {
        if (l_my_array[i] < l_my_array[i + 1])
            return false;
    }
    return true;
}

int main() {
    TYPE* array = new TYPE[LENGTH];

    ParallelGenerator(array, LENGTH, COUNT);

    //print(array, 0, LENGTH);

    ParallelSort(array, LENGTH, COUNT);

    //print(array, 0, LENGTH);

    mergeAll(array, LENGTH, COUNT);

    //print(array, 0, LENGTH);

    std::cout << std::boolalpha << "Sorted: " << validateSortedArray(array, LENGTH) << std::endl;
}