Sorting and Multithreading Write a program that sorts an array of random integer
ID: 3686768 • 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
Hi below i have written a sample code for Sorting and Multithreading for your reference,
//Sort a list of numbers using two separate threads
//by sorting half of each list separately then
//recombining the lists
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
#define NUMBER_OF_THREADS 3
void *sorter(void *params); /* thread that performs basic sorting algorithm */
void *merger(void *params); /* thread that performs merging of results */
int list[SIZE] = {7,12,19,3,18,4,2,6,15,8};
int result[SIZE];
typedef struct
{
int from_index;
int to_index;
} parameters;
int main (int argc, const char * argv[])
{
int i;
pthread_t workers[NUMBER_OF_THREADS];
/* establish the first sorting thread */
parameters *data = (parameters *) malloc (sizeof(parameters));
data->from_index = 0;
data->to_index = (SIZE/2) - 1;
pthread_create(&workers[0], 0, sorter, data);
/* establish the second sorting thread */
data = (parameters *) malloc (sizeof(parameters));
data->from_index = (SIZE/2);
data->to_index = SIZE - 1;
pthread_create(&workers[1], 0, sorter, data);
/* now wait for the 2 sorting threads to finish */
for (i = 0; i < NUMBER_OF_THREADS - 1; i++)
pthread_join(workers[i], NULL);
/* establish the merge thread */
data = (parameters *) malloc(sizeof(parameters));
data->from_index = 0;
data->to_index = (SIZE/2);
pthread_create(&workers[2], 0, merger, data);
/* wait for the merge thread to finish */
pthread_join(workers[2], NULL);
/* output the sorted array */
return 0;
}
void *sorter(void *params)
{
parameters* p = (parameters *)params;
//SORT
int begin = p->from_index;
int end = p->to_index+1;
int z;
for(z = begin; z < end; z++){
printf("The array recieved is: %d ", list[z]);
}
printf(" ");
int i,j,t,k;
for(i=begin; i< end; i++)
{
for(j=begin; j< end-i-1; j++)
{
if(list[j] > list[j+1])
{
t = list[j];
list[j] = list[j+1];
list[j+1] = t;
}
}
}
for(k = begin; k< end; k++){
printf("The sorted array: %d ", list[k]);
}
int x;
for(x=begin; x<end; x++)
{
list[x] = result[x];
}
printf(" ");
pthread_exit(0);
}
void *merger(void *params)
{
parameters* p = (parameters *)params;
//MERGE
int begin = p->from_index;
int end = p->to_index+1;
int i,j,t;
printf("list[1]: %d",list[1]);
printf("result[1]: %d",result[1]);
for(i=begin; i< end; i++)
{
for(j=begin; j< end-i; j++)
{
if(result[j] > result[j+1])
{
t = result[j];
result[j] = result[j+1];
result[j+1] = t;
}
}
}
int d;
for(d=0; d<SIZE; d++)
{
printf("The final resulting array is: %d ", result[d]);
}
pthread_exit(0);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.