Find Kth largest element in an array
  • randomizedselection
  • array
  • sorting
  • quicksort
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (3065)

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

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.