Median bestimmen

23.05.2018, 09:01

Zeaschi

Median bestimmen

Meine Frage:
Liebe Community,
ich versuche gerade den Median of Medians Algorithmus zu implementieren, jedoch ist dieser fehlerhaft. Vielleicht kann mir jemand sagen wo mein gedanklicher Fehler liegt

Meine Ideen:

code:

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;

    }

23.05.2018, 17:39

Auf diesen Beitrag antworten »

as_string

Erstens bin ich mir nicht sicher, ob das sinnvoll ist, immer das Array als Argument rum zu reichen. Geht das nicht einfacher?
Außerdem würde ich den Rückgabewert von median gleich als int und nicht als Arrays von int machen. Dann auch die Zeilen 12 und 13 zu

code:
1:	return data[(data.length) / 2];

umschreiben und eigentlich brauchst Du dann auch kein getMedian() mehr, weil das direkt durch median() ersetzt werden würde.

Aber der Fehler ist in Zeile 23:

code:
1:	right = left + median.length % 5;

Das müsste eigentlich:

code:
1:	right = left + data.length % 5;

sein.

Gruß
Marco

Neue Frage »

Antworten »

Median bestimmen

Verwandte Themen