_______________________________________________________________________ Write a
ID: 3604021 • Letter: #
Question
_______________________________________________________________________
Write a class that implements a parallel quick sort for an array of integers. Partition the array into four partitions and create four threads to sort the partitions in parallel. Each thread must sort only one of the four original partitions.
Create a class that extends Thread to implement your thread. Only create ONE thread class. Do not create a separate thread class for each thread.
After the four threads are started, the main program must wait (join) until all threads are done. The main program must then verify that the array is properly sorted.
The given Quicksort.java class contains several methods that should be useful.
Explanation / Answer
class QuickSort
{
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1);
for (int j=low; j<high; j++)
{
if (arr[j] <= pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void sort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.