Median of Medians

 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. 

Code from http://yiqi2.wordpress.com/2013/07/03/median-of-medians-selection-algorithm/
Also check http://javatroops.blogspot.com/2012/10/median-of-medians-to-find-kth-smallest.html

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

}

Quick Select:
http://ajeetsingh.org/2013/09/20/median-of-medians-find-kth-largest-element-from-a-large-un-sorted-array/

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;

 }

Read full article from Median of Medians