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 }