median

public class Problem1 {

public static void main(String[] args) {

int[] a = { 5, 5, 2, 3, 6, 7, 5, 5, 5};

int m = median(a);

System.out.println("For the array : {5, 5, 2, 3, 6, 7, 5, 5, 5}, the median is "+m);

System.exit(0);

}

//sort the array, and return the median

public static int median(int[] a) {

int temp;

int asize = a.length;

//sort the array in increasing order

//insertion sort

for (int i = 0; i < asize ; i++)

for (int j = i; j > 0; j--)

if (a[j] < a [j-1]) {

temp = a[j];

a[j] = a[j-1];

a[j-1]=temp;

}

/* one alternative way to sort

for (int j = 1; j< asize; j++) {

int v = a[j];

int i = j;

while (a[i-1]>v) {

a = a[i-1];

i--;

if (i<=0)

break;

}

a=v;

}

*/

/* another alternative way to sort

for (int i = 0; i < asize ; i++)

for (int j = i+1; j < asize; j++)

if (a > a[j]) {

temp = a;

a = a[j];

a[j] = temp;

}

*/

System.out.println("After sorting, the array becomes ");

for (int i = 0; i< asize; i++)

System.out.print(a+" ");

System.out.println();

//if array size is odd

if (asize%2 == 1)

return a[asize/2];

else //when array size is even

return ((a[asize/2]+a[asize/2 - 1])/2);

}

}

ma_biroteea at 2007-7-13 7:47:30 >

> Hi, the best thing to do is to use Sun's in-built

> QuickSort method Arrays.sort(). It sorts in the order

> of nlogn and is also robust in terms of static

> issues.

static issues?

> It can have memory issues (as it actually

> makes a clone of the Array and so on), but for

> incredibly large n, which is unlikely to be an issue

> in real-life data).

It only clones an Object array. Primitive arrays are not cloned.

>

> The code below is robust and should work fine.

>

Robust? For example?

Just some of the observations of your code.

1. Creating objects when they aren't required.

2. Using float, but calling it Double.

3. Your comparable doesn't handle infinity or NaN.

4. Your code requires creating an instance of the GetMedian object.

(The method should be static).

If you had a float array, the proper way would be:

public static float getMedian(float[] a) {

Arrays.sort(a);

int x = a.length / 2;

if (a.length % 2 == 0)

return (a[x] + a[x-1]) / 2;

return a[x];

}

However, this approach is O(nlogn)... but there are O(n) algorithms.

rkippena at 2007-7-13 7:47:30 >

> Thanks for the observation rkippen. It is rough (but

> works completely - what I meant by robust) code to

> show a O(nlogn) working - I BELIEVE THAT IS WHAT THE

> ORIGINAL QUESTION WAS.

No need to "shout"....

> I just hope it s useful to Goma.

No. Spoonfeeding is not helping. The only thing useful for someone as the OP is forcing him to read a textbook or to eat the thing (uncooked!).

Look at his question (is it even a question), roughly translated:

"Hey guys, I have to write an algoritm which can do X in at least O(n log(n)) time, but I've been to lazy to open my textbook and haven't attended class. Can anyone just do this for me? And no I haven't tried anything myself or else I definitely post my attemt to solve it with the question why it doesn't work. So if you'd just leave the solution here, I'll find it. And don't count on me replying to your posts."

All his threads are the same.

prometheuzza at 2007-7-13 7:47:30 >