/***********************************************************************
* 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));
}
}
}