JAVA

Code Skeleton:

//finds the Kth largest item in an unsorted array arr[], without sorting it public static int getKthLargest(int[] arr, int k) { //write here }

public static int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index determining the end of left partition for (int j=low; j

// put the pivot in its place int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;

return i+1; }

public static void main(String[] args){ int[] arr={1,5,2,4,10,10,66}; System.out.println(getKthLargest(arr,2));

int[] arr1={1,12,15,17,0,0,0}; int[] arr2={11,22,23}; merge(arr1,4,arr2, 3); System.out.println(Arrays.toString(arr1)); } }

static int getkthLargest (intll arr, int k) finds the Kth largest item in an unsorted array arr[l. Note that you are not allowed to sort the array and return the kth element. The idea is to call the partition method of quicksort, and compare the returned index with k. Based on the comparison, you can decide which subarray to continue searching (similar to binary search), or return if you have found the kth largest item. The code for partitioning is provided in the code skeleton. (50 points) static int getkthLargest (intll arr, int k) finds the Kth largest item in an unsorted array arr[l. Note that you are not allowed to sort the array and return the kth element. The idea is to call the partition method of quicksort, and compare the returned index with k. Based on the comparison, you can decide which subarray to continue searching (similar to binary search), or return if you have found the kth largest item. The code for partitioning is provided in the code skeleton. (50 points)