Write a class that implements a parallel quick sort for an array of integers. Pa

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.

Use Java's Date class to calculate the elapsed time for the sort operation and compare it to an unthreaded sort.

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

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.