/.vscode

/main

/main_single

/thread_algo

#include <iostream>

#include <pthread.h>

#include <time.h>

#include "thread_algo.h"

using std::cout;

vector<int> inputvect;

int sz = 50; // input size

typedef struct Data

{

vector<int> left;

vector<int> right;

} sort_thread;

void *Sort(void *arg)

{

vector<int> thread_vect = *((vector<int> *)arg);

int threshold = 10;

int size = thread_vect.size();

if (size <= threshold)

selectionSort(*((vector<int> *)arg));

else

{

//mergeSort(*((vector<int> *)arg), 0, size - 1);

quickSort(*((vector<int> *)arg), 0, size - 1);

}

return NULL;

}

void *merge_thread(void *arg)

{

Data sort_vect = *((Data *)arg);

vector<int> left = sort_vect.left;

vector<int> right = sort_vect.right;

inputvect.clear();

merge(inputvect, left, right);

return NULL;

}

int main()

{

clock_t t1, t2; // clock variable to compute time

// creating random vector

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

{

inputvect.push_back(rand() % 100);

}

cout << "unsorted array is: \n";

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

cout << inputvect[i] << " ";

cout << "\n";

// distribute the main VECTOR in two parts for each thread

vector<int> leftthread, rightthread;

int mid = (int)sz / 2;

cout << "mid:" << mid << "\n";

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

leftthread.push_back(inputvect[i]);

for (int i = mid; i < sz; i++)

rightthread.push_back(inputvect[i]);

t1 = clock(); // start time calculation (only thread execution is considered)

pthread_t sthread0, sthread1; // declaring sorting threads

pthread_create(&sthread0, NULL, Sort, &leftthread); // creating sorting threads

pthread_create(&sthread1, NULL, Sort, &rightthread);

if (sthread0 < 0 || sthread0 < 0) // checking for thread creation success

{

std::cerr << "error in sort thread creation";

}

else

{

// providing a join so that above two threads i.e. sorting threads

// so that we have sorted vectors before executing merge thread

pthread_join(sthread1, NULL);

pthread_t mergethread;

// storing left and right sorted vector

// in struct for passing to merge thread

Data Sort_thread = {leftthread, rightthread};

pthread_create(&mergethread, NULL, merge_thread, &Sort_thread); // creating merge thread

if (mergethread < 0) // checking for thread creation success

{

std::cerr << "error in mergethread creation";

}

else

{

pthread_join(mergethread, NULL); // providing a join to wait for merge thread execution

}

}

t2 = clock(); // end time calculation

cout << "Sorted Array \n";

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

cout << inputvect[i] << " ";

cout << "\n";

cout << "Time Taken=" << (t2 - t1);

return 0;

}

#include <iostream>

#include <time.h>

#include <pthread.h>

#include "thread_algo.h"

using std::cout;

void *singleThread_sort(void *arg)

{

vector<int> vect = *((vector<int> *)arg);

quickSort(*((vector<int> *)arg), 0, vect.size() - 1);

return NULL;

}

int main()

{

vector<int> inputvect;

int sz = 50;

clock_t t1, t2;

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

{

inputvect.push_back(rand() % 100);

}

cout << "unsorted array is: \n";

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

cout << inputvect[i] << " ";

cout << "\n";

t1 = clock();

pthread_t singlethread; // single thread creation to compare performance

pthread_create(&singlethread, NULL, singleThread_sort, &inputvect);

if (singlethread < 0)

{

std::cerr << "thread creation failed";

exit(1);

}

pthread_join(singlethread, NULL);

t2 = clock();

cout << "Sorted Array \n";

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

cout << inputvect[i] << " ";

cout << "\n";

cout << "Time Taken=" << (t2 - t1);

return 0;

}

#include "thread_algo.h"

void swap(int &xp, int &yp)

{

int temp = xp;

xp = yp;

yp = temp;

}

void merge(vector<int> &input, vector<int> &leftthread, vector<int> &rightthread)

{

int indexLeft = 0, // Initial index of left vector

indexRight = 0, // Initial index of rightvector

indexMerged = 0; // Initial index of merge vector

// Merge the sorted threads results back into original input while sorting

while (indexLeft < leftthread.size() && indexRight < rightthread.size())

{

if (leftthread[indexLeft] <= rightthread[indexRight])

{

input[indexMerged] = leftthread[indexLeft];

indexLeft++;

}

else

{

input[indexMerged] = rightthread[indexRight];

indexRight++;

}

indexMerged++;

}

// Copy the remaining elements of left thread result, if left

while (indexLeft < leftthread.size())

{

input[indexMerged] = leftthread[indexLeft];

indexLeft++;

indexMerged++;

}

// Copy the remaining elements of right thread result, if left

while (indexRight < rightthread.size())

{

input[indexMerged] = rightthread[indexRight];

indexRight++;

indexMerged++;

}

}

void merge(vector<int> &vector, int const left, int const mid,

int const right)

{

int leftvectorSize = mid + 1 - left;

int rightvectorSize = right - mid;

// temp vectors are created

std::vector<int> leftvector, rightvector;

// Copy data to temp vectors from main vector

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

leftvector.push_back(vector[left + i]);

for (int j = 0; j < rightvectorSize; j++)

rightvector.push_back(vector[mid + 1 + j]);

int indexLeft = 0, // Initial index of left vector

indexRight = 0; // Initial index of rightvector

int indexMerged = left; // Initial index of merge vector

// Merge the temp vector back into original vector while sorting

while (indexLeft < leftvectorSize && indexRight < rightvectorSize)

{

if (leftvector[indexLeft] <= rightvector[indexRight])

{

vector[indexMerged] = leftvector[indexLeft];

indexLeft++;

}

else

{

vector[indexMerged] = rightvector[indexRight];

indexRight++;

}

indexMerged++;

}

// Copy the remaining elements of left vector , if left

while (indexLeft < leftvectorSize)

{

vector[indexMerged] = leftvector[indexLeft];

indexLeft++;

indexMerged++;

}

// Copy the remaining elements of right vector, if left

while (indexRight < rightvectorSize)

{

vector[indexMerged] = rightvector[indexRight];

indexRight++;

indexMerged++;

}

}

void mergeSort(vector<int> &vect, int l, int h)

{

if (l >= h)

return; // Returns recursively

int mid = l + (h - l) / 2;

mergeSort(vect, l, mid);

mergeSort(vect, mid + 1, h);

merge(vect, l, mid, h);

}

void selectionSort(vector<int> &vect)

{

int min_idx;

int n = vect.size();

// One by one move boundary of unsorted subvector

for (int i = 0; i < (n - 1); i++)

{

// Find the minimum element in unsorted subvector

min_idx = i;

for (int j = i + 1; j < n; j++)

if (vect[j] < vect[min_idx])

min_idx = j;

// Swap the found minimum element with the first element

if (min_idx != i)

swap(vect[min_idx], vect[i]);

}

}

int partition(vector<int> &vector, int low, int high)

{

// select the rightmost element as pivot

int pivot = vector[high];

// pointer for greater element

int i = (low - 1);

// traverse each element of the vector

// compare them with the pivot

for (int j = low; j < high; j++)

{

if (vector[j] <= pivot)

{

// if element smaller than pivot is found

// swap it with the greater element pointed by i

i++;

// swap element at i with element at j

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

}

}

// swap pivot with the greater element at i

swap(vector[i + 1], vector[high]);

// return the partition point

return (i + 1);

}

void quickSort(vector<int> &vector, int low, int high)

{

if (low < high)

{

// find the pivot element such that

// elements smaller than pivot are on left of pivot

// elements greater than pivot are on righ of pivot

int pi = partition(vector, low, high);

// recursive call on the left of pivot

quickSort(vector, low, pi - 1);

// recursive call on the right of pivot

quickSort(vector, pi + 1, high);

}

}

#ifndef __thread_algo__h

#define __thread_algo__h

#include <vector>

#include<ostream>

using std::vector;

using std::ostream;

class intVector{

public:

intVector(){};

intVector(int sz);

bool operator<(const intVector &v);

bool operator>(const intVector &v);

bool operator==(const intVector &v);

bool operator>=(const intVector &v);

bool operator<=(const intVector &v);

friend ostream& operator<<(ostream &os,const intVector&v );

private:

int size;

vector<int> vect;

};

void merge(vector<int> &arr, vector<int> &left, vector<int> &right);

void swap(int &x, int &y);

void merge(vector<int> &arr, int low, int mid, int high);

void mergeSort(vector<int> &vect, int l, int h);

void quickSort(vector<int> &vect, int l, int h);

int partition(vector<int> &array, int low, int high);

void selectionSort(vector<int> &arr);

#endif