Saturday, 18 July 2015

Find kth largest or smallest element in unsorted array

Question :Find Kth element(largest/smallest) in an unsorted array

Solution: Using pivot finding method of QuickSort we can find Kth element's position it will give Kth smallest element, to find Kth largest modify the program to find smallest from the end. Following program finds Kth largest in an un-sorterd array:
 
/**
 * @author Vikky.Agrawal
 *
 */
public class LargestK {

 int arr[];
 int length;
 
 LargestK(){
  arr=new int[]{16,17,18,4,12,9,5,1};
  this.length=arr.length;
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  new LargestK().operate();
 }
 
 
 public void operate(){
  int k=1;
  System.out.println(k+" th largest in array : "+findKthLargest(arr, 0, length-1, length-k));
  
 }
 
 
 //Using QuickSort's pivot finding method
 public int findKthLargest(int[] arr, int p, int q, int k) {

  if(p==q){
   if(k==p){
    return arr[p];
   }else{
    return -1;
   }
  } 
  
  else if (p < q) {
   int pivot = findPivot(arr, p, q);
   
   if (pivot == k)
    return arr[pivot];
   if (pivot > k) {
    return findKthLargest(arr, 0, pivot-1, k);
   } else {
    return findKthLargest(arr, pivot + 1, length-1, k);
   }
  }else{
   return -1;
  }
  
 }
 
 public int findPivot(int[] arr, int p, int r){
  
  int x=arr[r];
  int i=p-1; 
  
  for(int j=p ;j<r; j++){
   if(arr[j]<= x){
    i++;
    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
  }  
  
  arr[r]=arr[i+1];
  arr[i+1]=x;
  return i+1;
 }
}


Complexity Analysis:
Time required to find pivot = O(n)
In average cases only half of the array will be searched(assuming pivot will divide the array in half), time required to divide will be T(n/2).
Hence total time to find Kth largest T(n) = T(n/2)+O(n) = O(n) average case.
In worst case pivot might divide the array in 1 an n-1 always, hence worst case time will be T(n) = T(n-1)+O(n) = O(n2).