Quick Select

https://rosettacode.org/wiki/Quickselect_algorithm#Java

 private static <E extends Comparable<? super E>> int partition(E[] arr, int left, int right, int pivot) {
  E pivotVal = arr[pivot];
  swap(arr, pivot, right);
  int storeIndex = left;
  for (int i = left; i < right; i++) {
   if (arr[i].compareTo(pivotVal) < 0) {
    swap(arr, i, storeIndex);
    storeIndex++;
   }
  }
  swap(arr, right, storeIndex);
  return storeIndex;
 }
 
 private static <E extends Comparable<? super E>> E select(E[] arr, int n) {
  int left = 0;
  int right = arr.length - 1;
  Random rand = new Random();
  while (right >= left) {
   int pivotIndex = partition(arr, left, right, rand.nextInt(right - left + 1) + left);
   if (pivotIndex == n) {
    return arr[pivotIndex];
   } else if (pivotIndex < n) {
    left = pivotIndex + 1;
   } else {
    right = pivotIndex - 1;
   }
  }
  return null;
 }

http://www.geekviewpoint.com/java/search/quickselect

 public int quickselect(int[] G, int k) {

  return quickselect(G, 0, G.length - 1, k - 1);

}

 

private int quickselect(int[] G, int first, int last, int k) {

  if (first <= last) {

    int pivot = partition(G, first, last);

    if (pivot == k) {

      return G[k];

    }

    if (pivot > k) {

      return quickselect(G, first, pivot - 1, k);

    }

    return quickselect(G, pivot + 1, last, k);

  }

  return Integer.MIN_VALUE;

}

 

private int partition(int[] G, int first, int last) {

  int pivot = first + new Random().nextInt(last - first + 1);

  swap(G, last, pivot);

  for (int i = first; i < last; i++) {

    if (G[i] > G[last]) {

      swap(G, i, first);

      first++;

    }

  }

  swap(G, first, last);

  return first;

}

 

private void swap(int[] G, int x, int y) {

  int tmp = G[x];

  G[x] = G[y];

  G[y] = tmp;

}

http://www.cs.ucf.edu/~dmarino/ucf/java/QuickSelect.java

 public static int rQuickSelect(StudentNode[] a, int i, int j, int k){// start, end
    
  int p;
  
  // if there are still elements that need to be examined run
  // partition and quicksort on the half that is relevant
  if(i < j){
   
   p = QuickSelect.partitionArray(a, i, j);
   
   // p is equal to k (kRank) return p
   if(p == k)
    return p;

   // else determine which half of the array needs to be sent to 
   // quick select recursively
   else{
    if(k < p)
     return(QuickSelect.rQuickSelect(a, i, p-1, k));
    else
     return(QuickSelect.rQuickSelect(a, p+1, j, k));
   }
  }
  
  // else return the kth value
  else
   return k;
 }
 
 //---------------------------------------------------------------------
 // partitionArray: static method that uses a partition index element,
 //                 pVal, to partition the array to values less than
 //                 the value at pVal on the left and greater than on 
 //                 the right 
 //---------------------------------------------------------------------
 public static int partitionArray(StudentNode[] a, int i, int j){
 
  
  int pVal;
  StudentNode temp;
  
  // set the partition element as the value in array a at index
  // i; this is the first element in the section of the array being
  // currently partitioned
  pVal = i;
    
  // increment i to next value
  i++;
  
  // move i to the right while the value in array a at index i is
  // greater than the partition element
  while(a[i].gpa > a[pVal].gpa)
   i++;
  
  // move j to the left while the value in the array at index j is
  // less than the partition element
  while(a[j].gpa < a[pVal].gpa)
   j--;

  // if i is still less than j swap the values at indexes i and j
  if(i < j){
   temp = a[i];
   a[i] = a[j];
   a[j] = temp;
  
  // else swap value at pVal with value at j and return index j
  }else{
   temp = a[pVal];
   a[pVal] = a[j];
   a[j] = temp;
  }
  
  return j;
 
 }