Programming assignment 5.3. Count sort is a simple serial sorting algorithm that
ID: 3599919 • Letter: P
Question
Programming assignment 5.3.
Count sort is a simple serial sorting algorithm that can be implemented as follows:
void Count sort(int a[], int n) {
int i, j, count;
int temp = malloc(n sizeof(int));
for (i = 0; i < n; i++) {
count = 0;
for (j = 0; j < n; j++)
if (a[j] < a[i])
count++;
else if (a[j] == a[i] && j < i)
count++;
temp[count] = a[i];
}
memcpy(a, temp, n sizeof(int));
free(temp);
} /* Count sort */
The basic idea is that for each element a[i] in the list a, we count the number of elements in the list that are less than a[i]. Then we insert a[i] into a temporary list using the subscript determined by the count. There’s a slight problem with this approach when the list contains equal elements, since they could get assigned to the same slot in the temporary list. The code deals with this by incrementing the count for equal elements on the basis of the subscripts. If both a[i] == a[j] and j <i, then we count a[j] as being “less than” a[i].
After the algorithm has completed, we overwrite the original array with the temporary array using the string library function memcpy.
a. If we try to parallelize the for i loop (the outer loop), which variables should be private and which should be shared?
b. If we parallelize the for i loop using the scoping you specified in the previous part, are there any loop-carried dependences? Explain your answer.
c. Can we parallelize the call to memcpy? Can we modify the code so that this part of the function will be parallelizable?
d. Write a C program that includes a parallel implementation of Count sort.
e. How does the performance of your parallelization of Count sort compare to serial Count sort? How does it compare to the serial qsort library function?
Explanation / Answer
1. The below programe uses parallel Sorting approach to place eachitem at proper index based on Count Sort Algorithm 2. For Parallel sorting we use Threads (we use Pthreads which are popular threads in Linux O.S C programming) 3. Threads will execute parallely so that they may over write some global arrays like Array of elements and Temp Array in our case 4. So prtoect from this problem we use Mutex for Thread Synchronization . Any thread will lock mutex when it wants to write any global array (if already locked then calling lock again will block the thread for excution until the Mutex is unlocked by present locked thread) 5. So there will be no overwriting or corruption of aray 6. This programmes not checking performance or execution time. You can use your own approach. 7. Please comment if any doubts Programme :- -------------------- #include #include #include #include #include #include //Structure to pass arguements to Threads , a Item in Array and its index in Array struct arguement { int item; int idx; }; //Mutex to make all threads write the Temp or Main Array without any conflicts using lock/release method pthread_mutex_t lock; //Variable to store total array elements int itemcount = 0; //Main Array pointer int *a; //Temp Array pointer int * temp; //Sort Function void count_sort() ; //Sort Sub Function void * sort_sub(void * args); int main(int argc, char *argv[]) { //Get Total items from user printf("Enter Size of Array "); scanf("%d",&itemcount); //Allocate array based on size a = (int *)malloc(sizeof(int)*itemcount); //Set all elements in Temp to 0 temp = (int *)malloc(sizeof(int)*itemcount); memset(temp,0,sizeof(int)*itemcount); //Get Elements from user for(int i = 0 ; i item = a[i]; //Create a Pthread that runs in parallel to sort a Item from Base arrary int err = pthread_create(&tid, NULL, &sort_sub, (void *)args); if (err != 0) printf(" can't create thread :[%s]", strerror(err)); pthread_join(tid, NULL); } } //Sort Sub Function void * sort_sub( void * args){ //Get Given Item in Array and its index from the Arguements struct arguement *input = (struct arguement *)args; int idx = input->idx; int item = input->item; int index = 0; //Find out index where the given item will fit using count sort algorithm for(int i = 0 ; i the value at index then if(a[i]Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.