001    /*
002     * Median
003     * 
004     * Copyright (c) 2001, 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.util;
009    
010    /**
011     * Pick the median value from an array (or an interval of an array).
012     * @author Marco Schmidt
013     * @since 0.5.0
014     */
015    public class Median
016    {
017            /**
018             * This class is supposed to have static methods only.
019             * To hide any constructor, we define an empty private one.
020             */
021            private Median()
022            {
023            }
024    
025            /**
026             * Exchange two elements in the argument array.
027             * A temporary variable is used so that a[i1] will
028             * hold the value that was previously stored at a[i2]
029             * and vice versa.
030             * 
031             * @param a the array in which two elements are swapped
032             * @param i1 index of the first element
033             * @param i2 index of the second element
034             * @throws ArrayIndexOutOfBoundsException if either i1 or i2 are
035             *  not valid index values into a (from 0 to a.length - 1)
036             */
037            public static void swap(int[] a, int i1, int i2)
038            {
039                    int temp = a[i1];
040                    a[i1] = a[i2];
041                    a[i2] = temp;
042            }
043    
044            /**
045             * Find the median value of the specified interval of the argument array.
046             * The interval starts at index <code>from</code> and goes to
047             * <code>to</code>; the values at these positions are included.
048             * Note that the array will be modified while searching, so you might want
049             * to backup your data.
050             * <p>
051             * This implementation is a port of the C function from
052             * <code>quickselect.c</code>, provided at <a target="_top" 
053             * href="http://ndevilla.free.fr/median/">http://ndevilla.free.fr/median/</a>.
054             * The page is a good resource for various median value algorithms, including
055             * implementations and benchmarks.
056             * <p>
057             * The original code on which this class is based was written in C++
058             * by Martin Leese.
059             * It was ported to C and optimized by Nicolas Devillard (author of the 
060             * above mentioned page).
061             * The algorithm is from <em>Numerical recipes in C</em>, Second Edition,
062         * Cambridge University Press, 1992, Section 8.5, ISBN 0-521-43108-5.
063             * <p>
064             *
065             * @param a the array
066             * @param from the index of the start of the interval in which the median value will be searched
067             * @param to the index of the end of the interval in which the median value will be searched
068             * @return the median value
069             */
070            public static int find(int[] a, int from, int to)
071            {
072                    int low = from;
073                    int high = to;
074                    int median = (low + high) / 2;
075                    do
076                    {
077                            if (high <= low)
078                            {
079                                    return a[median];
080                            }
081                            if (high == low + 1)
082                            {
083                                    if (a[low] > a[high])
084                                    {
085                                            swap(a, low, high);
086                                    }
087                                    return a[median];
088                            }
089                            int middle = (low + high) / 2;
090                            if (a[middle] > a[high])
091                            {
092                                    swap(a, middle, high);
093                            }
094                            if (a[low] > a[high])
095                            {
096                                    swap(a, low, high);
097                            }
098                            if (a[middle] > a[low])
099                            {
100                                    swap(a, middle, low);
101                            }
102                            swap(a, middle, low + 1);
103                            int ll = low + 1;
104                            int hh = high;
105                            do
106                            {
107                                    do
108                                    {
109                                            ll++;
110                                    }
111                                    while(a[low] > a[ll]);
112                                    do
113                                    {
114                                            hh--;
115                                    }
116                                    while(a[hh] > a[low]);
117                                    if (hh < ll)
118                                    {
119                                            break;
120                                    }
121                                    swap(a, ll, hh);
122                            }
123                            while(true);
124                            swap(a, low, hh);
125                            if (hh <= median)
126                            {
127                                    low = ll;
128                            }
129                            if (hh >= median)
130                            {
131                                    high = hh - 1;
132                            }
133                    }
134                    while(true);
135            }
136    }