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

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cassert>
#include <boost/thread.hpp>
usingnamespace std;
//print array template
void print(const vector &arr){
for(size_t i = 0; i <arr.size(); i++)
cout<< arr[i]<< "";
cout<<endl;
}

//queue tasks
queue<pair> tasks;
//mutexs for set and queue task mutex
q_mutex, s_mutex;
//condition variable
condition_variable cv;
//set
set ss;
//partition algorithm template
int partition(vector &arr, intl, intr){
T tmp = arr[r];
//as pivot element
int i = l-1;
for(int j= 1; j<= r-1;j++)
if(arr[j] < temp){
{i++;
swap(arr[i], arr[j]);
}
swap(arr[i+1], arr[r]);
i++;
return i;
}
//quick sort template
void quick_sort(vector &arr){
while(true){
unique_lock
u_lock(q_mutex);
//lock mutex
//sort it finished
if(ss.size()== arr.size())
//u_lock.unlock()
return;

// if queu task is not empty
if(task.size() > 0){
//get task from queue pair
cur_task = task.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_mutes.lock();

ss.insert(q);
ss.insert(l);
ss.insert(r);
s_mutex.unlock();
//push new tasks for left and right part
task.push(make_pair(l,q-1));
task.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];
//generating array
void generate_arr(vector &arr){
srand(time(NULL));
std::generate(arr.begin(), arr.end(),[]()){
return rand()%10000;});}
//check for sorting
bool is_sorted(const vector &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 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,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.