# Median Suchalgorithmus



## dayaftereh (20. Apr 2010)

Hey, ich bin gerade an eine Projekt am Optimiren und zwar ich muss aus Arrays welche aus ints bestehen sehr heufig (30 mal die Sekunde) den Median berechnen! die Arrays haben eine Länge von 1e3 bi 1e6 ,hier bei ist es egal ob es zwei oder ein ergebnis gibt! die Felder sind nicht sortiert! So hier ist meine Algorithmus! könnte ihr mal drüber schauen ob das ganze so weit Klappt oder ob jemand noch ein paar optimirungen vorschlagen kann!:


```
...
	medianSuch(array, 0, (array.length - 1))
...
	private int medianSuch(int[] array, int l, int r) {
		// Median bestimmen
		int p = (l + r) / 2;
		// Sotiren des Feldes so das Median in der Mitte
		int pn = partition(array, 0, array.length - 1, p);

		if (l == r) {
			// Median gefunden
			return array[array.length / 2];
		}

		if (pn - 1 >= array.length / 2) {
			// k >= n/2 ,dann suche Links
			return medianSuch(array, l, pn);
		} else if (pn + 1 <= array.length / 2) {
			// g <= n/2 ,dann suche Rechts
			return medianSuch(array, pn + 1, r);
		} else {
			// Median Gefunden
			return array[pn];
		}
	}

	private int partition(int[] array, int l, int r, int p) {
		// pn = Position des Median
		int pn = l;
		int pv = array[p];

		// Median-Element an das Ende Verschieben um Platz zu haben
		swap(array, p, r);

		// Elemente kleiner oder gleich Median-Element nach vorn tauschen
		for (int i = 0; i < r; i++) {
			if (array[i] <= pv) {
				// pn nach jedem tausch erhöhen
				swap(array, pn++, i);
			}
		}

		// Median zurück tauschen
		swap(array, r, pn);
		// neue Median Position zurück geben
		return pn;
	}

	private void swap(int[] array, int idx1, int idx2) {
		int tmp = array[idx1];
		array[idx1] = array[idx2];
		array[idx2] = tmp;
	}
```

Ich glaube die Komplexität ist O(n) bitte Korrigirt mich wenn ich hier falsch Liege und könnte jemand den Algorithmus noch mal kontrolieren!

Danke Schon mal!


----------



## SlaterB (20. Apr 2010)

sieht aus wie ein Quicksort,
Quicksort ? Wikipedia
von da kannst du noch bisschen übernehmen, z.B. muss der Median p nicht (l + r) / 2 sein, genau r ist in einem unsortierten Array nicht schlechter,
dann sparst du dir auch das Verschieben ans Ende

die Schleife von 36-40 beginnt immer bei 0, es wird auch immer der Parameter l = 0 übergeben,
entweder weglassen oder ich denke das müsste auch mit dem richtigen l funktionieren, dann auch die Schleife bei l beginnen,
evtl. die Schleife generell mehr wie bei Quicksort arbeiten lassen, siehe Link, 
deine Schleife scheint aber auch gut zu funktionieren, 
bei meinem kurzen Test war am Anfang recht häufig i == pn bzw. pn++, das könntest du prüfen und das swap sparen, falls du auf solche Performance-Details Wert legst


die Komplexität dürfte genauso bei n*log(n) liegen, 
dass du nach der Hälfte der Arbeit aufhörst ist für die Komplexität kein Faktor


----------



## Marco13 (20. Apr 2010)

Konkrete Verbesserungsvorschläge habe ich ... kaum... das ist ja direkt aus Wikipedia übernommen. Dort ist aber auch was mit "Median of Medians" beschrieben, wodurch es worst-case-O(n) werden soll.

Ein Verbesserungsvorschlag: Sorg' dafür, dass es auch mit ungeraden Arraygrößen funktioniert


----------



## ice-breaker (20. Apr 2010)

ehrlich gesagt, kann ich nicht ganz nachvollziehen, was der Algorithmus machen soll


----------



## dayaftereh (20. Apr 2010)

Also Danke erstmal allen für die Tips!

Der Algoritmus soll den Mitterwert der ints in der Array suchen!Das mache ich so! Ich nehme mir eine Pivo-Element (wie bei QuickSort) und sortiere meine Feld so das alle Kleine sind wie meine Pivo-Element Links vom Element stehen und alle die Größer meine Pivo-Elements sind rechts Stehen! dan schaue ich nach der umsortierung wo meine Pivo Element ist! dan prüfe ich ob k >= n/2 ist, wenn ja dan im linke Bereich weiter nach dem Median suchen, wenn g <= n/2 ist dan im rechten Bereich weiter suchen! g = Pivo-Element Position +1 und k = Pivo-Element Position - 1; und dan das ganze von Vornen! eine Pivo-Element nehmen ,soritiren usw.

Wenn jetzt keine Bedinung zu trieft dan habe ich den Median oder der Bereich wo ich suche ist <= 0


----------

