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

I tried this homework and there are errors.

Please check my code and fix errors.

:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <boost/thread.hpp>
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 < right ; i++) {
if (data[i] <= pivotValue){
swap(data[i], data[storeIndex]);
storeIndex++;
}
}
swap(data[storeIndex], data[right]);
return storeIndex;
}
};

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 < 1000000; i++)
data[i] = rand();

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

Explanation / Answer

please find the below code:

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <algorithm>

#include <cassert>

#include <boost/thread.hpp>

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 < right ; i++) {

if (data[i] <= pivotValue){

swap(data[i], data[storeIndex]);

storeIndex++;

}

}

swap(data[storeIndex], data[right]);

return storeIndex;

}

};

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 < 1000000; i++)

data[i] = rand();

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.