Massive Algorithms: Median of Medians

http://javatroops.blogspot.com/2012/10/median-of-medians-to-find-kth-smallest.html
Given an array of unsorted integers find the Kth smallest element using "Median of Medians".
This method is guaranteed to work in max linear time

if you just get the student who is ranked

50th in the class. Now in another single pass (

O(n)), you can just compare the marks of the rest of the students with the selected student.
http://javatroops.blogspot.com/2012/10/median-of-medians-to-find-kth-smallest.html


	private static int select(Integer[] a, int k) {
	if (a.length <= 10)
	{
	Arrays.sort(a);
	return a[k-1];
	}
	int n = a.length;
	//partition L into subsets S[i] of five elements each
	// (there will be n/5 subsets total).
	List<Integer[]> list = new ArrayList<Integer[]>();
	// don't need temp list.
	int cnt = 0;
	int m = n/5;
	for( int i = 0; i < m; i++ ) {
	Integer[] arr = new Integer[5];
	for( int j = 0; j < 5; j++ ) {
	if( cnt == n )
	break;
	arr[j] = a[cnt++];
	}
	Arrays.sort(arr);
	list.add(arr);
	}

	Integer[] x = new Integer[m];
	for (int i = 0; i< m; i++ ) {
	x[i] = list.get(i)[2];
	}

	int v = x[0];
	if(x.length > 2) {
	v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];
	}

	// partition L into L1<M, L2=M, L3>M ==> we can combine these two steps
	Integer[] l = partition_l( a, v );
	Integer[] r = partition_r( a, v );

	if( k == l.length+1 ) {
	return v;
	} else if( k <= l.length ){
	return select(l,k);
	} else {
	return select(r,k-l.length-1);
	}

	}

	private static Integer[] partition_l( Integer[] a, int pivot ) {
	if( a.length == 0)
	return a;
	int j = 0;
	Integer[] b = new Integer[a.length];
	for( int i = 0; i < a.length; i++ ) {
	if(a[i] < pivot) {
	b[j++] = a[i];
	}
	}
	Integer[] l = new Integer[j];
	System.arraycopy(b, 0, l, 0, j);
	return l;
	}

	private static Integer[] partition_r( Integer[] a, int pivot ) {
	if( a.length == 0)
	return a;
	int j = 0;
	Integer[] b = new Integer[a.length];
	for( int i = 0; i < a.length; i++ ) {
	if(a[i] > pivot) {
	b[j++] = a[i];
	}
	}
	Integer[] r = new Integer[j];
	System.arraycopy(b, 0, r, 0, j);
	return r;
	}

private int find(int[] a, int s, int n, int k ) {

    // start point s, length n, find k-th number

    if ( n == 1 && k == 1 )

        return a[s];

    int m = (n+4) /5;

    int[] mid = new int[m];

    for (int i=0; i<m; i++) {

        int t = s+i*5;      // 5-elements block pointer

        if ( n-t > 4 ) {

            sort(a, t, 5);      // sort 5 elements

            mid[i] = a[t+2];

}

        else {      // less than 5 left

            sort(a, t, n-t);    // sort the rest 

            mid[i] = a[t+(n-t-1)/2];

}

}

    int pivot = find(mid, 0, m, (m+1)/2);

    for (int i=0; i<n; i++) {        // find pivot location

        if (a[s+i] == pivot ) {

            swap(a, s+i, s+n-1);

            break;

}

}

    int pos = 0;

    for (int i=0; i<n-1; i++) {      // using pivot to part

        if ( a[s+i] < pivot ) {

            if ( i != pos )

                swap(a, s+i, s+pos);

            pos++;

}

}

    swap(a, s+pos, s+n-1);

    if ( pos == k-1 )

        return pivot;

    else if ( pos > k-1 )

        return find(a, s, pos, k);

    else

        return find(a, s+pos+1, n-pos-1, k-pos-1);

}

int findKthElement(int[] input, int K){

           int lo = 0, hi = input.length - 1;

           while (hi > lo) {

              int i = partition(input, lo, hi);

           if (i > k)

              hi = i - 1;

           else if (i < k)

              lo = i + 1;

           else

              return input[i];

}

        return input[lo];

}

int partition(int[] input, int lo, int hi) {

          int i = lo;

          int j = hi + 1;

          int pivot = input[lo];

          while (true) {

             while (less(input[++i], pivot))

                 if (i == hi) 

                        break;

             while (less(pivot, input[--j]))

                    if (j == lo) 

                         break;

             if (i >= j)

                    break;

             exchange(input[i], input[j]);

}

          exchange(input[lo], input[j]);

          return j;

}

Labels