What's the equivalent 'nth_element' function in Java?

Question

I don't want get a sorted array, just nth element's value. For example, given the array

 a = [20, 5, 1, -3] 

I'd like to be able to query

nth_element(a,2) = 1

In C++, there is a function std::nth_element that can do this. Is there an equivalent Java function?

Thanks!

Answer 1

The Java standard library does not contain an equivalent of the C++ nth_element algorithm. The closest that you'll get would be to use Collections.sort.

Alternatively, you could try implementing your own version of this function. You could implement nth_elementby doing a standard sort and calling Collections.sort, though depending on your time requirements this may be too slow. There are many specialized algorithms for performing this sort of reordering that are called selection algorithms and the Wikipedia page on the subject has several good examples. Empirically, the fastest algorithm is called quickselect and is based on the quicksort algorithm; it runs in expected O(n) time but can degrade to O(n²) for pathologically bad inputs. There is a famous (and notoriously complex) algorithm sometimes called the median-of-medians algorithm that runs in worst-case O(n), but has a high constant factor that prevents it from being used in practice.

Hope this helps!

Answer 2

Here is a Java implementation of nth_element:

class Nth_element
{ 
    static void nth_element_helper2(double[] arr, int beg, int end)
    {
        for(int i = beg + 1; i < end; i++)
        {
            for(int j = i; j > beg; j--)
            {
                if(arr[j - 1] < arr[j])
                    break;
                double t = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = t;
            }
        }
    }

    static void nth_element_helper(double[] arr, int beg, int end, int index)
    {
        if(beg + 4 >= end)
        {
            nth_element_helper2(arr, beg, end);
            return;
        }
        int initial_beg = beg;
        int initial_end = end;

        // Pick a pivot (using the median of 3 technique)
        double pivA = arr[beg];
        double pivB = arr[(beg + end) / 2];
        double pivC = arr[end - 1];
        double pivot;
        if(pivA < pivB)
        {
            if(pivB < pivC)
                pivot = pivB;
            else if(pivA < pivC)
                pivot = pivC;
            else
                pivot = pivA;
        }
        else
        {
            if(pivA < pivC)
                pivot = pivA;
            else if(pivB < pivC)
                pivot = pivC;
            else
                pivot = pivB;
        }

        // Divide the values about the pivot
        while(true)
        {
            while(beg + 1 < end && arr[beg] < pivot)
                beg++;
            while(end > beg + 1 && arr[end - 1] > pivot)
                end--;
            if(beg + 1 >= end)
                break;

            // Swap values
            double t = arr[beg];
            arr[beg] = arr[end - 1];
            arr[end - 1] = t;

            beg++;
            end--;
        }
        if(arr[beg] < pivot)
            beg++;

        // Recurse
        if(beg == initial_beg || end == initial_end)
            throw new RuntimeException("No progress. Bad pivot");
        if(index < beg) // This is where we diverge from QuickSort. We only recurse on one of the two sides. This is what makes nth_element fast.
            nth_element_helper(arr, initial_beg, beg, index);
        else
            nth_element_helper(arr, beg, initial_end, index);
    }

    static double nth_element(double[] arr, int index)
    {
        nth_element_helper(arr, 0, arr.length, index);
        return arr[index];
    }

    public static void main(String[] args)
    {
        double[] arr = { 9, 7, 1, 5, 6, 4, 3, 2, 8, 0, 10 };
        if(nth_element(arr, 5) == 5)
            System.out.println("seems to work");
        else
            System.out.println("broken");
    }
}