Class 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 Detail

      • Median

        private Median()
        This class is supposed to have static methods only. To hide any constructor, we define an empty private one.
    • 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 swapped
        i1 - index of the first element
        i2 - 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 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