Below is the program. Implement the "TODO" package Lab07; import java.util.*; import java.util.InputMismatchException; /**  * A class for implementing and testing kthItem method  *  * @author atb  * @version 10/9/2018  */  public class KthElement { /**  * Task: Sorts the first, middle, and last elements of an  * array into ascending order.  *  * @param a an array of Comparable objects  * @param first the integer index of the first array element; first >= 0  * @param mid the integer index of the middle array element  * @param last the integer index of the last array element;  * last - first >= 2, last  */  private static > void sortFirstMiddleLast(T[] a, int first, int mid, int last) { orderTwoItems(a, first, mid); // make a[first] /**  * Task: Orders two given array elements into ascending order  * so that a[i]  *  * @param a an array of Comparable objects  * @param i an integer >= 0 and  * @param j an integer >= 0 and  */  private static > void orderTwoItems(T[] a, int i, int j) { if (a[i].compareTo(a[j]) > 0) swap(a, i, j); } // end orderToItems /**  * Task: Swaps the array elements a[i] and a[j].  *  * @param a an array of objects  * @param i an integer >= 0 and  * @param j an integer >= 0 and  * assumes that i != j  */  private static  void swap(T[] a, int i, int j) { T temp = a[i]; a[i] = a[j]; a[j] = temp; } // end swap /**  * Task: Partitions an array as part of quick sort into two subarrays  * called Smaller and Larger that are separated by a single  * element called the pivot.  * Elements in Smaller are left of the pivot and  * Elements in Larger are right of the pivot and >= pivot.  *  * @param a an array of Comparable objects  * @param first the integer index of the first array element;  * first >= 0  * @param last the integer index of the last array element;  * last >= first; last  * @return the index of the pivot  */  private static > int partition(T[] a, int first, int last) { int mid = first + (last - first) / 2; sortFirstMiddleLast(a, first, mid, last); int pivotIndex = mid; if (last - first + 1 > 3) { // Assertion: The pivot is a[mid]; a[first] = pivot, so do not compare these two array entries // with pivot. // Move pivot to next-to-last position in array swap(a, mid, last - 1); pivotIndex = last - 1; T pivotValue = a[pivotIndex]; // Determine subarrays Smaller = a[first..endSmaller] // and Larger = a[endSmaller+1..last-1] // such that entries in Smaller are = pivotValue; initially, these subarrays are empty int indexFromLeft = first + 1; int indexFromRight = last - 2; boolean done = false; while (!done) { // Starting at beginning of array, leave entries that are = pivotValue; you will find one, // since last entry is >= pivot while (a[indexFromLeft].compareTo(pivotValue)  pivot; // locate first entry that is  0) indexFromRight--; assert a[indexFromLeft].compareTo(pivotValue) >= 0 && a[indexFromRight].compareTo(pivotValue) /**************************************************************  * KTH ORDER STATISTIC - ALGORITHM THAT USES PARTITION  * ARRAY MAY BE SORTED OR UNSORTED  **************************************************************/   /**  * Task: Find the kth item of the first n items in sorted order  *  * @param a an array of Comparable objects  * @param n an integer >= 0 and less than or equal to a.length  * @param k an integer >= 0 and less than or equal to n  */  public static > T kthItem(T[] a, int k, int n) { return kthItem(a, k, 0, n - 1); } // end kthItem /**  * Recursively finds the kth item in a array of items  * utilizing partitioning strategy of quick sort.  *  * @param a an array of Comparable objects  * @param k an integer >= 0 that is the position of the item to return.  * @param first an integer >= 0 that is the index of the first  * array element to consider  * @param last an integer >= 0 that is the index of the last  * array element to consider  */  private static > T kthItem(T[] a, int k, int first, int last) { //TODO Project1 //System.out.println("call: " + k + " " + first + " " + last + " "); // IMPLEMENT kthItem METHOD RECURSIVELY // HINT: call partition(a, first, last) method to get the pivotIndex return null; //THIS IS A STUB } // end kthItem public static int getNextPrime(int integer) { // if even, add 1 to make odd if (integer % 2 == 0) { integer++; } // test odd integers while (!isPrime(integer)) { integer = integer + 2; } return integer; } // end getNextPrime private static boolean isPrime(int integer) { boolean result; boolean done = false; // 1 and even numbers are not prime if ((integer == 1) || (integer % 2 == 0)) { result = false; } // 2 and 3 are prime else if ((integer == 2) || (integer == 3)) { result = true; } else // integer is odd and >= 5 { assert (integer % 2 != 0) && (integer >= 5); // a prime is odd and not divisible by every odd integer up to its square root result = true; // assume prime for (int divisor = 3; !done && (divisor * divisor >> kthItem found median at index " + k + " with value of " + result + "   Written in Java: We have an unsorted array of integers and we want to find the value of an element at index k that would be there if the array was sorted I. The simplest way to find the kth element is to sort the data and take the value that is at the index k. But sorting does more than necessary to solve this problem. You need to find only the kth smallest entry in the collection for an appropriate value of k. We can use the partitioning strategy of quick sort to find the kth smallest entry in the array: After choosing a pivot and forming the sub-arrays Smaller and Larger s pivot pivot e pivot Smaller Larger you can draw one of the following three conclusions: 1) if pivot index is the same as k, the kh smallest element is the entry at the pivot index 2) if Smaller sub-array contains k or more entries, it must contain the kth smallest entry 3) otherwise the kth element is in Larger sub-array For example, let us assume that we are looking for the smallest entry that would be at index 3 if the array was sorted. The initial array is: 3 5 0461 2 4.After the first partition it will look as follow:  Written in Java: We have an unsorted array of integers and we want to find the value of an element at index k that would be there if the array was sorted I. The simplest way to find the kth element is to sort the data and take the value that is at the index k. But sorting does more than necessary to solve this problem. You need to find only the kth smallest entry in the collection for an appropriate value of k. We can use the partitioning strategy of quick sort to find the kth smallest entry in the array: After choosing a pivot and forming the sub-arrays Smaller and Larger s pivot pivot e pivot Smaller Larger you can draw one of the following three conclusions: 1) if pivot index is the same as k, the kh smallest element is the entry at the pivot index 2) if Smaller sub-array contains k or more entries, it must contain the kth smallest entry 3) otherwise the kth element is in Larger sub-array For example, let us assume that we are looking for the smallest entry that would be at index 3 if the array was sorted. The initial array is: 3 5 0461 2 4.After the first partition it will look as follow