++ Multithread version of QuickSort: code implementation. Hello there, I have an

Question

++ Multithread version of QuickSort: code implementation.

Hello there, I have an assignment due for my C++ data structure class.

I find it too hard for me to code the program to run properly and I desperately need expert-level help.

I have been trolled for too many times now, and I hope you're the one that can take my question seriously...

Here is the assignment:

(remove spaces) sourceforge . net/projects /boost/files/ boost/1.63.0/

This is the link to C++ boost libraries where you can download the full boost distribution and then extract boost_1_63_0/boost/math directory somewhere in the include path for your compiler or project.

I really don't understand the boost part so that's the most I can explain.

If you don't quite understand the boost part you may just skip it. But the program should still work.

Thank you in advance and I really appreciate your help.

In this assignment you're going to implement a multithreaded version of Quicksort, where the recursive calls will be replaced by other threads. Well be using the Boost.Thread library discussed in class. This code creates an array with one million random elements, and then sorts it include Kcstdlib Hinclude Kboost/thread. hpp int main int data [1000000 for (int i 0; i 1000000 it data[i] rand return 0;

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;

template <typename A>
void display(const vector<A> &array)
{
for (size_t c = 0; c < array.size(); c++)
cout << array[c] << " ";
cout << endl;
}

queue< pair<int, int> > works;
mutex queue, small;
condition_variable cv;
set<int> ss;

template <typename A>
int part(vector<A> &array, int l1, int bb)
{
A tempo = array[bb];
int c = l1 - 1;

for (int ee = l1; ee <= bb - 1; ee++)
if (array[ee] < tempo)
{
c++;
swap(array[c], array[ee]);   
}

swap(array[c + 1], array[bb]);
c++;
return c;
}

template <typename A>
void Q_cs(vector<A> &array)
{
while (true)
{
unique_lock<mutex> u_lock(queue);

if ( ss.size() == array.size() )
return;

if ( works.size() > 0 )
{
pair<int, int> cur_task = works.front();
works.pop();

int l1 = cur_task.first, bb = cur_task.second;

if (l1 < bb)
{
int vv = part(array, l1, bb);

small.lock();
ss.insert(vv);
ss.insert(l1);
ss.insert(bb);
small.unlock();

works.push( make_pair(l1, vv - 1) );
works.push( make_pair(vv + 1, bb) );

cv.notify_one();
}
}
else
cv.wait(u_lock);
}
}

const int ARRAY_SIZE = 100000;
const int THREAD_CNT = 8;

thread thrs[THREAD_CNT];

void genARR(vector<int> &array)
{
srand(time( NULL ));

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

bool isSort(const vector<int> &array)
{
for (size_t c = 0; c < array.size() - 1; c++)
if ( ! (array[c] <= array[c + 1]) )
return false;
return true;
}

int main()
{
  
clock_t Start, fin;

vector<int> array(ARRAY_SIZE);

genARR(array);

cout << endl << "Finished Creating!" << endl << endl;

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

display(array);

cout << endl << endl;

cout << "Checking the sorting is finished! The result is " << (isSort(array) == 0? "false": "true") << "." << endl << endl;

works.push( make_pair(0, array.size() - 1) );

Start = clock();

for (int c = 0; c < THREAD_CNT; c++)
thrs[c] = thread( Q_cs<int>, ref(array) );

fin = clock();

for (auto& th : thrs)
th.join();

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

cout << " Displaying Array after sorting" << endl << endl;
display(array);

cout << endl << endl;

cout << "Checking Sorting is finished! The result obtained is " << (isSort(array) == 0? "false": "true") << "." << endl << endl;

cout << "Runtime: " << (double)(fin - Start) / CLOCKS_PER_SEC << endl;

return 0;
}

Hope it helps......

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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