net.sourceforge.jiu.util

Class Median


public class Median
extends java.lang.Object

Pick the median value from an array (or an interval of an array).
Author:
Marco Schmidt
Since:
0.5.0

Constructor Summary

Median()
This class is supposed to have static methods only.

Method Summary

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.

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

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 index from and goes to to; 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 array
from - the index of the start of the interval in which the median value will be searched
to - the index of the end of the interval in which the median value will be searched
Returns:
the median value

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 swapped
i1 - index of the first element
i2 - index of the second element