### Find Kth largest element in an array randomizedselection array sorting quicksort    Posted: 6 years ago Updated: 5 years ago Edit answers (1) views (3090)

Suppose you are given an array of N elements indexed from 1 to N . Design an efficient algorithm to find the $$k^{th}$$ largest element.

## Posted Answers

 Posted: 6 years ago 0 0 Edit We can use quickselect(A,k) algorithm : Pick any random integer from the unsorted array and mark it as the pivot . Split the array into A1 (for smaller elements than $$pivot$$) and A2 (for bigger elements than $$pivot$$). If ( k < = length of A2), then required range is in A2 - return quickselect(A2,k) . If ( k > length of A2), then required range is in A1 - return quickselect(A2,k - length(A2)) . Otherwise, return pivot . public int findKthLargest (int[] list, int k){ int left = 0; int right = list.length - 1; while (true){ int pivotIndex = (left + right)/2; int newPivot = partition(list,left,right,pivotIndex); if (newPivot == k) return list[newpivot]; elseif (newPivot < k) left = newPivot+1; else right = newPivot-1; }}private static int partition (int[] list, int left, int right, int pivot){ int pivotValue= list[pivot]; /* Put the pivot value at the end */ swap(list,pivot,right); int storePosition = left; for(int i = left; i < right; i++){ if(list[i] < pivotValue){ swap(list,i,storePosition); storePosition++; } } swap(list, storePosition, right); return storePosition;}private static void swap(int[] list, int a, int b){ int temp = list[a]; list[a] = list[b]; list[b] = temp; }
You need to Sign In to post your solution.