Package net.sourceforge.jiu.util
Class Median
- java.lang.Object
-
- net.sourceforge.jiu.util.Median
-
public class Median extends Object
Pick the median value from an array (or an interval of an array).- Since:
- 0.5.0
- Author:
- Marco Schmidt
-
-
Constructor Summary
Constructors Modifier Constructor Description private
Median()
This class is supposed to have static methods only.
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static int
find(int[] a, int from, int to)
Find the median value of the specified interval of the argument array.static void
swap(int[] a, int i1, int i2)
Exchange two elements in the argument array.
-
-
-
Method Detail
-
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
-
-