## A randomized divide-and-conquer algorithm

There is nothing new here. My Java code to find the $k^{th}$ smallest element in an array(Algorithms book by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani). The code is written based on the pseudo-code.

I am using Google guava here.

Ints.toArray( less )


This is the algorithm definition.

$selection(S,k) = \begin{cases} selection(S_L,k), & \mbox{if } k\le |S_L|\\ v, & \mbox{if } |S_L| < k \le |S_L| + |S_v|\\ selection(S_R,k-|S_L|-|S_v|, & \mbox{if } k\ge |S_L|+|S_v| \end{cases}$

import com.google.common.primitives.Ints;

import java.util.ArrayList;
import java.util.Random;

import static java.util.Arrays.sort;

public class KThLargestSelection {

private Random r = new Random();

static int[] a1 = new int[]{ 0,2,7,3,4,9};

public int findKThLargest(  int[] a, int k ){

int pivot = getPivot(a);

ArrayList<Integer> less = new ArrayList<>();
ArrayList<Integer> equal = new ArrayList<>();
ArrayList<Integer> great = new ArrayList<>();

for( int value : a ){
if ( value < pivot){
} else if ( value == pivot){
}else if ( value > pivot){
}
}
if (k <= less.size()) {
return findKThLargest (Ints.toArray( less ), k);
}else if (k <= less.size() + equal.size()){
return  pivot;
}else
return   findKThLargest (Ints.toArray( great  ), k - less.size() - equal.size());

}

private int getPivot( int[] data ){
int[] highLow = new int[0];

System.out.println("getPivot [" + data.length + "] " + toStringArray(data));
highLow = new int[] { data[0],data[data.length - 1] };

if( data.length >= 3){
sort(new int[]{data[r.nextInt(2)],
data[r.nextInt(2)],
data[r.nextInt(2)]});
}
return highLow[ 1 ];
}

private String toStringArray(int[] data){
StringBuilder sb = new StringBuilder();
for( int i = 0 ; i < data.length ; i ++ ){
sb.append( data[i] + " ");
}
return sb.toString();
}

public static void main( String... s){
KThLargestSelection l = new KThLargestSelection();
System.out.println( l.findKThLargest(a1, 1));
}
}