Data Structure in C++

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

Parallelization

I tried this homework and there are errors.

Please check my code and fix errors.

:

#include #include #include #include #include #include using namespace std;

struct qsort_thread { unsigned int* data; unsigned int left, right; unsigned int size; unsigned int p;

void operator()() { int pivotValue = data[p]; swap(data[p], data[right]); int storeIndex = left;

for (int i = left ; i

void seq_qsort(int* data, int left, int right) { if (right > left) { int pivotIndex = left + (right - left)/2; pivotIndex = qsort_thread(data, left, right, pivotIndex); seq_qsort(data, left, pivotIndex-1); seq_qsort(data, pivotIndex+1, right); } }

void par_qsort(int* data, int left, int right, int size){ if (right > left) { int pivotIndex = left + (right - left)/2; pivotIndex = qsort_thread(data, left, right, pivotIndex);

if (size-- > 0) { struct qsort_thread arg = {data, left, pivotIndex-1, size}; thread_group threads; int ret = threads.create_thread(&thread, NULL, quicksort_thread, &arg);

par_qsort(data, pivotIndex+1, right, size); }

else { seq_qsort(data, left, pivotIndex-1); seq_qsort(data, pivotIndex+1, right); } }

}

/* int main() { int data[1000000]; for(int i = 0; i

return 0; } */

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