# Nth element (Java)

**Other implementations**:**Java**| Python

Find the nth-largest element in an unsorted list.

## [edit] theory

The obvious way to find the nth-largest element in a list is to sort it first, then examine the nth index. However, that approach does more work than is required, as we only care about the element in the nth place, not the permutation of any elements before or after. By modifying a Quicksort to only recurse on the sublist of interest, we avoid much of the work of a full sort.

(for an alternative approach, see *An efficient implementation of Blum, Floyd, Pratt, Rivest, and Tarjan’s worst-case linear selection algorithm*)

*Question: Suppose n to be the minimum or maximum element. What relation does this algorithm bear to a 1-dimensional version of Quickhull (Python, arrays)?*

## [edit] practice

We start off in classic quicksort style — we choose a **pivot**, and create lists of elements which sort **above** or **below** the pivot.

<<define qnth>>=publicstatic<TextendsComparable<?superT>> T qnth(List<T> sample,intn){T pivot = sample.get(0); List<T> below =newArrayList<T>(), above =newArrayList<T>();for(T s : sample){if(s.compareTo(pivot)< 0)below.add(s);elseif(s.compareTo(pivot)> 0)above.add(s);}inti = below.size(), j = sample.size()- above.size();

At this point, **i** and **j** would (if it were sorted) index into **sample** as follows:

hence we need only recurse on the segment containing the nth element.

<<define qnth>>=if(n < i)returnqnth(below, n);elseif(n >= j)returnqnth(above, n-j);elsereturnpivot;}

## [edit] wrapping up

Finally we wrap the function up in a class with a main function which, if run from the command line, checks (for an element from the middle of a random list) that **qnth** produces the same result as sorting the list and then selecting the *n*th element.

<<QNth.java>>=import java.util.List;import java.util.ArrayList;import java.util.Collections;publicclassQNth{define qnthpublicstaticvoidmain(String[]args){intn = 64, mid = 32; List<Double> sample =newArrayList<Double>();for(inti = 0; i < n; i++)sample.add(Math.random());doublepartial = qnth(sample, mid); Collections.sort(sample);doublesorted = sample.get(mid); System.out.println("" + partial + " " + sorted + " " +(partial == sorted));}}

The output should be similar to:

0.579906140785445 0.579906140785445 true

Download code |