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!
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(n2) 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!
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");
}
}
Quickselect algorithm is now implemented in AlgART library: https://bitbucket.org/DanielAlievsky/algart/src/master/src/main/java/net/algart/arrays/ArraySelector.java You can just use it via Maven, as described here: http://algart.net/java/AlgART/
There are the corresponding methods in class java.lang.reflect.Array1, see its documentation
Example:
var array = new int[] { 20, 5, 1, -3};
var value = java.lang.reflect.Array.getInt(array, 2);
1 - not to confuse with java.sql.Array
In Java I think you have to implement it, something like this:
Integer nth_smallest_element(Integer[] originalArray, n) {
if (n >= originalArray.length)
throw new RuntimeException("Invalid index");
// Don't pass in your array, if you don't want it to be modified. Instead add them all later.
List<Integer> copyList = new ArrayList<Integer>();
copyList.addAll(originalArray);
Collections.sort(copyList);
return copyList.get(n);
}
