Data Structure in C++ Implement a multithreaded version of Quicksort, where the

Question

Data Structure in C++

Implement a multithreaded version of Quicksort, where the recursive calls will be replaced by other threads.

Parallelization

This code creates an array with one million random elements, and then sorts it #include int main() int data 1000000]; for (int i 0; i K 1000000; i++) data[i] rand() return 0 Your first task is to just implement a normal. recursive quicksort. void seq-qsort(int* data, int size Using that as a guideline, implement a multithreaded quicksort. Because its kind of wasteful to spawn a new thread for arrays that are very small. make your parallel version switch to the recursive version if size 16 void par-qsort(int* data, int size In order to implement this, as discussed in class, you'll have to create a "callable class (a class that overloads operator and pass it to the boost::thread constructor struct qsort-thread unsigned int start, end; void operator Partition the range lstart,end) with pivot p unsigned int p Spawn new threads for the left/right partitions This class will contain information about a single "step of the quicksort operation e.. the range of values to sort) and when called will perform a partition step and then spawn two new threads to sort the left and right partitions. The algorithm is complete when allthreads have finished executing (note that threads may finish in a completely different order from that in which you started them!) Compare the runtimes of the two versions: is either noticably faster? The server is a single-core machine, and thus you won't probably see any difference there.) When you compile. youll have to link with the Boost.Thread library

Explanation / Answer

#include <thread>

#include <chrono>

#include <mutex>

#include <condition_variable>

#include <iostream>

#include <queue>

#include <vector>

#include <set>

#include <ctime>

#include <algorithm>

using namespace std;

//print an array

template <typename T>

void print(const vector<T> &arr)

{

    for (size_t i = 0; i < arr.size(); i++)

        cout << arr[i] << " ";

    cout << endl;

}

//queue task

queue< pair<int, int> > tasks;

//mutexs for set and queue task

mutex q_mutex, s_mutex;

//condition variable

condition_variable cv;

//set

set<int> ss;

//partition algorithm

template <typename T>

int partition(vector<T> &arr, int l, int r)

{

    T tmp = arr[r]; //as pivot element

    int i = l - 1;

    for (int j = l; j <= r - 1; j++)

        if (arr[j] < tmp)

        {

            i++;

           swap(arr[i], arr[j]);      

        }

    swap(arr[i + 1], arr[r]);

    i++;

    return i;

}

//quick sort

template <typename T>

void quick_sort(vector<T> &arr)

{

    while (true)

    {

        unique_lock<mutex> u_lock(q_mutex); //lock mutex

        //sort is fineshed

        if ( ss.size() == arr.size() ) //u_lock.unlock()

            return;

        //if queue task is not empty

        if ( tasks.size() > 0 )

        {

            //get task from queue

            pair<int, int> cur_task = tasks.front();           

            tasks.pop();

            int l = cur_task.first, r = cur_task.second;       

            if (l < r)

            {

                int q = partition(arr, l, r); //split array

                //Add indexes in set

                s_mutex.lock();

                ss.insert(q);

                ss.insert(l);

                ss.insert(r);

                s_mutex.unlock();

                //push new tasks for left and right part

                tasks.push( make_pair(l, q - 1) );

                tasks.push( make_pair(q + 1, r) );

                //wakeup some thread which waiting

                cv.notify_one();

            }

        }

        else

            //if queue is empty

            cv.wait(u_lock);

    }

}

//Size array

const int ARR_SIZE = 100000;

//Count threads

const int THREAD_COUNT = 8;

thread thrs[THREAD_COUNT];

//generatin array

void generate_arr(vector<int> &arr)

{

    srand(time( NULL ));

    std::generate(arr.begin(), arr.end(), [](){return rand() % 10000; });

}

//check for sorting

bool is_sorted(const vector<int> &arr)

{

    for (size_t i = 0; i < arr.size() - 1; i++)

        if ( ! (arr[i] <= arr[i + 1]) )

            return false;

    return true;

}

int main()

{

    //time

    clock_t start, finish;

    vector<int> arr(ARR_SIZE);

    //generate array

    generate_arr(arr);

    cout << endl << "Generating finished!" << endl << endl;

    cout << "Array before sorting" << endl << endl;

    //Before sorting

    print(arr);

    cout << endl << endl;

    cout << "Checking is_sorted finished! The result is " << (is_sorted(arr) == 0? "false": "true") << "." << endl << endl;

    //add task

    tasks.push( make_pair(0, arr.size() - 1) );

    //==================================================

    start = clock();

    for (int i = 0; i < THREAD_COUNT; i++)

        thrs[i] = thread( quick_sort<int>, ref(arr) );

    finish = clock();

    //==================================================

    for (auto& th : thrs)

        th.join();

    cout << "Sorting finished!" << endl << endl;

    cout << "Array after sorting" << endl << endl;

    //After sorting

    print(arr);

    cout << endl << endl;

    cout << "Checking is_sorted finished! The result is " << (is_sorted(arr) == 0? "false": "true") << "." << endl << endl;

    cout << "Runtime: " << (double)(finish - start) / CLOCKS_PER_SEC << endl;

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.