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);
}
}
|
