Sorting and Multithreading Write a program that sorts an array of random integer
ID: 3686819 • Letter: S
Question
Sorting and Multithreading
Write a program that sorts an array of random integers sequentially and then using multithreading. Use POSIX thread library on UNIX.
Should take the following command line argurments:
1) The array size. This would be positive integer between 1 and 100,000,000. Check for boundaries!
2) Number of threads. This would be positive integer between 1 and 16.
3) Sorting Algorithm. Choose between 'I' for InsertionSort or 'Q' for QuickSort.
Follow these steps:
1) Fill array with rand numbers
2) Based on the number of threads (T), compute the indices for dividing the array into T equal parts. For example, if the array size (N) is 1000 and T is 2, the indices will be 0, 499, 999.
3) Sort sequentially by applying sorting algorithm to each part of the array. Then combine the sorted parts into one sorted array using an O(n) algorithm.
4) Apply an O(n) algorithm to check if the array has been sorted correctly. Then print a message indicating correct/incorrect sorting.
5) Refill array with rand numbers.
6) Sort using multi-threading. Should be done the same way as sequential sorting with the difference being that the sorting of each part is done in a separate thread. Combining the sorted parts into one sorted array should be done in the main (parent) thread after all child threads have completed. Therefore, the parent thread must wait for all child threads.
7) Apply an O(n) algorithm to check if array has been sorted correctly. Then print a message indicating correct/incorrect sorting.
------
Use code below. However, there may be some erros present. Possibly in QuickSort. Be sure to check for errors, check bugs.
#include <sys/timeb.h>
#include <stdio.h>
#include <stdlib.h>
long gRefTime;
long GetMilliSecondTime(struct timeb timeBuf)
{
long mliScndTime;
mliScndTime = timeBuf.time;
mliScndTime *= 1000;
mliScndTime += timeBuf.millitm;
return mliScndTime;
}
long GetCurrentTime(void) {
long crntTime=0;
struct timeb timeBuf;
ftime(&timeBuf);
crntTime = GetMilliSecondTime(timeBuf);
return crntTime;
}
void SetTime(void) {
gRefTime = GetCurrentTime();
}
long GetTime(void) {
long crntTime = GetCurrentTime();
return (crntTime - gRefTime);
}
void InsertionSort(int data[], int size) {
int i, j, temp;
for(i=1; i<size; i++) {
temp = data[i];
for(j=i-1; j>=0 && data[j]>temp; j--)
data[j+1] = data[j];
data[j+1] = temp;
}
}
void QuickSort(int data[], int p, int r) {
int q;
if(p >= r) return;
q = Partition(data, p, r);
QuickSort(data, p, q-1);
QuickSort(data, q+1, r);
}
int Partition(int data[], int p, int r) {
int i, j, x, pi;
pi = Rand(p, r);
Swap(data[r], data[pi]);
x = data[r];
i = p-1;
for(j=p; j<r; j++)
{
if(data[j] < x) {
i++;
Swap(data[i], data[j]);
}
}
Swap(data[i+1], data[r]);
return i+1;
}
void Swap(int& x, int& y) {
int temp = x;
x = y;
y = temp;
}
int Rand(int x, int y) {
int range = y-x+1;
int r = rand() % range;
r += x;
return r;
}
Explanation / Answer
main.cpp #include #include #include #include #include #include #include using namespace std; int arraySize; int numThreads; int *mainArray; int *threadedArray; int *finalArray; int value; string sortAlg; long gRefTime; int indices[16][2]; pthread_attr_t attr; pthread_t threads[16]; int thread_args[16]; void calculateIndices(); int* combineArrays(int arr[], int finalArr[]); void insertionSort(int arr[], int arraySize); void *intertionSortThreaded(void *index); void *quickSortThreaded(void *index); void QuickSort(int arr[], int left, int right); int Partition(int data[], int p, int r); void Swap(int& x, int& y); int Rand(int x, int y); void validateArray(int arr[]); void printArray(int arr[]); long GetMilliSecondTime(struct timeb timeBuf); long GetCurrentTime(void); void SetTime(void); long GetTime(void); int main(int argc, char* argv[]){ /*validate if there are not enough arguments*/ if (argc < 4){ printf("Not enough arguments. Usage: %c , Array size, Number of threads, Sorting algorithm (I or Q) ", argv[0]); return -1; } /*validate if there are too many arguments*/ else if (argc > 4){ printf("Too many arguments. Usage: %s , Array size, Number of threads, Sorting algorithm (I or Q) ", argv[0]); return -1; } /*validate the array size*/ arraySize = atoi(argv[1]); if (arraySize > 100000000 || arraySize < 1){ printf("Not a valid array size. Must be between 1 to 100,000,000 "); return -1; } /*validate the number of threads*/ numThreads = atoi(argv[2]); if (numThreads > 16 || numThreads < 1){ printf("Not a valid number of threads. Must be between 1 to 16 "); return -1; } /*validate sorting algorithm options*/ sortAlg = argv[3]; if ((sortAlg.compare("i") != 0) && (sortAlg.compare("I") != 0) && (sortAlg.compare("q") != 0) && (sortAlg.compare("Q") != 0)){ printf("Not a valid sorting algorithm option. Must be either I or Q "); return -1; } /*declares the sizes of the arrays*/ mainArray = new int[arraySize]; threadedArray = new int[arraySize]; finalArray = new int[arraySize]; calculateIndices(); /*fills two arrays with random numbers*/ for (int i = 0; iRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.