Date: Thursday, October 8, 2020.
Here is the function bucket sort that you may have seen in C243.
const unsigned int m = largest(array) + 1;
void bucketSort(unsigned int a[], unsigned int n)
{
int buckets[m], i, j, k;
for (j = 0; j < m; j++)
buckets[j] = 0;
for (i = 0; i < n; i++)
buckets[a[i]]++;
for (i = 0, j = 0; j < m; j++)
for (k=0; k < buckets[j]; k++)
a[i++] = j;
} // bucketSort()
The bucket sort works with the idea of counting how many times each
value occurs in the array, and storing that information in the
buckets. Then it reconstructs the original array from the
buckets. Here is an illustration of this operation:
a. Examine each of the 3 for loops and decide whether they can be done in parallel and how you would divide them between processes or threads.
b. Is there a need for any barriers between them?
a. What difference would it make if this was implemented with pthreads or with MPI (shared memory or distributed)?
Upload a file with the answers to points a, b, and c to Canvas, Assignments, Exercise 2, or type it directly in the submission input box.