package sort; import java.util.Random; public class QuickSort { /* * Returns an array of the specified length containing * random integers. */ public static int[] randomArray(int size) { Random rand = new Random(); int[] a = new int[size]; for(int i=0; i a[i]) { return false; } } return true; } /* * Sorts given array into ascending order. */ public static void quickSort(int[] a) { quickSort(a, 0, a.length - 1); } /* * Sorts numbers from start index to end index, inclusive, * in given array into ascending order. */ public static void quickSort(int[] a, int start, int end) { if (start < end) { int pivot = partition(a, start, end); quickSort(a, start, pivot - 1); quickSort(a, pivot + 1, end); } } /* * Partitions numbers from start index to end index, inclusive, * in given array so that all numbers < pivot are to the left * of pivot and all numbers >= pivot are to the right of pivot. * * Pivot element is selected using middle-of-nine method. * * Returns the index of the pivot. */ public static int partition(int[] a, int start, int end) { swap(a, start, pivot(a, start, end)); int lastSmaller = start; for (int i = start + 1; i <= end; i++) { if (a[i] < a[start]) { lastSmaller++; swap(a, i, lastSmaller); } } swap(a, lastSmaller, start); return lastSmaller; } /* * Returns the middle of the three given elements using * a stylish conditional operator. Feast your eyes. */ private static int mid3(int[] a, int x, int y, int z) { return a[x] < a[y] ? (a[y] < a[z] ? y : a[x] < a[z] ? z : x) : (a[y] > a[z] ? y : a[x] > a[z] ? z : x); } /* * Selects a pivot element using middle-of-nine method. * Returns the index of the pivot element. */ private static int pivot(int[] a, int start, int end) { int size = end - start + 1; int mid = (start + end) / 2; if (size > 7) { if (size > 40) { int step = size / 8; start = mid3(a, start, start + step, start + 2 * step); mid = mid3(a, mid - step, mid, mid + step); end = mid3(a, end - 2 * step, end - step, end); } mid = mid3(a, start, mid, end); } return mid; } /* * Swaps two integers at indexes i and j in array a. */ private static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } 

_______________________________________________________________________

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.