1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
|
/*
* Median
*
* Copyright (c) 2001, 2002, 2003 Marco Schmidt.
* All rights reserved.
*/
package net.sourceforge.jiu.util;
/**
* Pick the median value from an array (or an interval of an array).
* @author Marco Schmidt
* @since 0.5.0
*/
public class Median
{
/**
* This class is supposed to have static methods only.
* To hide any constructor, we define an empty private one.
*/
private Median()
{
}
/**
* 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.
*
* @param a the array in which two elements are swapped
* @param i1 index of the first element
* @param 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)
*/
public static void swap(int[] a, int i1, int i2)
{
int temp = a[i1];
a[i1] = a[i2];
a[i2] = temp;
}
/**
* Find the median value of the specified interval of the argument array.
* The interval starts at index <code>from</code> and goes to
* <code>to</code>; the values at these positions are included.
* Note that the array will be modified while searching, so you might want
* to backup your data.
* <p>
* This implementation is a port of the C function from
* <code>quickselect.c</code>, provided at <a target="_top"
* href="http://ndevilla.free.fr/median/">http://ndevilla.free.fr/median/</a>.
* The page is a good resource for various median value algorithms, including
* implementations and benchmarks.
* <p>
* 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 <em>Numerical recipes in C</em>, Second Edition,
* Cambridge University Press, 1992, Section 8.5, ISBN 0-521-43108-5.
* <p>
*
* @param a the array
* @param from the index of the start of the interval in which the median value will be searched
* @param to the index of the end of the interval in which the median value will be searched
* @return the median value
*/
public static int find(int[] a, int from, int to)
{
int low = from;
int high = to;
int median = (low + high) / 2;
do
{
if (high <= low)
{
return a[median];
}
if (high == low + 1)
{
if (a[low] > a[high])
{
swap(a, low, high);
}
return a[median];
}
int middle = (low + high) / 2;
if (a[middle] > a[high])
{
swap(a, middle, high);
}
if (a[low] > a[high])
{
swap(a, low, high);
}
if (a[middle] > a[low])
{
swap(a, middle, low);
}
swap(a, middle, low + 1);
int ll = low + 1;
int hh = high;
do
{
do
{
ll++;
}
while(a[low] > a[ll]);
do
{
hh--;
}
while(a[hh] > a[low]);
if (hh < ll)
{
break;
}
swap(a, ll, hh);
}
while(true);
swap(a, low, hh);
if (hh <= median)
{
low = ll;
}
if (hh >= median)
{
high = hh - 1;
}
}
while(true);
}
}
|