Package net.sourceforge.jiu.util
Class Median
java.lang.Object
net.sourceforge.jiu.util.Median
Pick the median value from an array (or an interval of an array).
- Since:
- 0.5.0
- Author:
- Marco Schmidt
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
Median()
This class is supposed to have static methods only. -
Method Summary
-
Constructor Details
-
Median
private Median()This class is supposed to have static methods only. To hide any constructor, we define an empty private one.
-
-
Method Details
-
swap
public static void swap(int[] a, int i1, int i2) Exchange two elements in the argument array. A temporary variable is used so that a[i1] will hold the value that was previously stored at a[i2] and vice versa.- Parameters:
a
- the array in which two elements are swappedi1
- index of the first elementi2
- index of the second element- Throws:
ArrayIndexOutOfBoundsException
- if either i1 or i2 are not valid index values into a (from 0 to a.length - 1)
-
find
public static int find(int[] a, int from, int to) Find the median value of the specified interval of the argument array. The interval starts at indexfrom
and goes toto
; the values at these positions are included. Note that the array will be modified while searching, so you might want to backup your data.This implementation is a port of the C function from
quickselect.c
, provided at http://ndevilla.free.fr/median/. The page is a good resource for various median value algorithms, including implementations and benchmarks.The original code on which this class is based was written in C++ by Martin Leese. It was ported to C and optimized by Nicolas Devillard (author of the above mentioned page). The algorithm is from Numerical recipes in C, Second Edition, Cambridge University Press, 1992, Section 8.5, ISBN 0-521-43108-5.
- Parameters:
a
- the arrayfrom
- the index of the start of the interval in which the median value will be searchedto
- the index of the end of the interval in which the median value will be searched- Returns:
- the median value
-