Quickselect: Find the Top k Values
by Isai Damier, Android Engineer @ Google

/***********************************************************************
 * Author: Isai Damier
 * Title: Find the Greatest k Scores
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a list of cores, find the top k scores.
 *
 * Time Complexity: O(n log n)
 * 
 * Sample Input: {21,3,34,5,13,8,2,55,1,19}; 4
 * Sample Output: 55,34,21,19
 * 
 * Technical Details: Author: Isai Damier
 * Title: Find the Top k values
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a list of cores, find the top k scores.
 *
 * Time Complexity: O(n log n)
 * 
 * Sample Input: {21,3,34,5,13,8,2,55,1,19}; 4
 * Sample Output: {55, 34, 21, 19}
 * 
 * Technical Details: This selection problem is a classic and so has
 *   many very good solutions. In fact, any sorting algorithm can be
 *   modified to solve this problem. In the worst case, the problem
 *   can indeed be reduced to a sorting problem: where the collection
 *   is first sorted and then the element at indices 0 to k-1 are
 *   retrieved.
 *   
 *   Presently the problem is solved using a modified version of
 *   quicksort called quickselect.
 **********************************************************************/ 
 public int[] quickselectTopK(int[] G, int k) {
  quickselect(G, 0, G.length - 1, k - 1);
  return Arrays.copyOfRange(G, 0, k);
}

private void quickselect(int[] G, int first, int last, int k) {
  if (first <= last) {
    int pivot = partition(G, first, last);

    if (pivot > k) {
      quickselect(G, first, pivot - 1, k);
    } else if (pivot < k) {
      quickselect(G, pivot + 1, last, k);
    }
  }
}

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;
}

package algorithms;

import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class SearchAlgorithmsTest {
  
  /**
   * Test of findTopKCandidates method, of class SearchAlgorithms.
   */
  @Test
  public void testFindTopK() {
    System.out.println("quickselectTopK");
    int[] G = {21, 3, 34, 5, 13, 8, 2, 55, 1, 19};
    SearchAlgorithms search = new SearchAlgorithms();
    int[][] expResult = {{55, 34},
                         {55, 34, 21},
                         {55, 34, 21, 19},
                         {55, 34, 21, 19, 13},
                         {55, 34, 21, 19, 13, 8},
                         {55, 34, 21, 19, 13, 8, 5},
                         {55, 34, 21, 19, 13, 8, 5, 3},
                         {55, 34, 21, 19, 13, 8, 5, 3, 2},
                         {55, 34, 21, 19, 13, 8, 5, 3, 2, 1}
    };
    for (int[] exp : expResult) {
      assertArrayEquals(exp, search.quickselectTopK(G, exp.length));
    }
  }
}