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:
|
public int getMedian(int[] data) {
int[] m = median(data);
return m[0];
}
private int[] median(int[] data) {
int[] median = new int[(data.length + 4) / 5];// Berechne wie viele Gruppen es gibt
int right;
if (data.length <= 5) {
{ sort(data, 0, data.length);
median[0] = data[(data.length) / 2];
return median;
}
} else {
//Partitionieren
for (int i = 0; i < median.length; i++) {
int left = 5 * i;// Abstände der Gruppen
if (i == median.length - 1) {
right = left + median.length % 5;
data = sort(data, left, right);
median[i] = data[left + ((right - left+1 ) / 2)];
} else {
right = left + 5;//Das erste Elemente dass nicht mehr dazu gehört}
data = sort(data, left, right);
median[i] = data[left +2];
}
}
return median(median);
}
}
public int[] sort(int[] arr, int s, int e) {//Bubbelsort zum sortieren des partitionen sollte eig passen bereits an vielen random erzeugen array getestet
for (int i = s; i < e; i++)
for (int j = s; j < e - i - 1; j++)
if (arr[j] > arr[j + 1]) {
// swap temp and arr[i]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
return arr;
}
|