[C++] Funktion um Median zu berechnen?
- Themenstarter Romsl
- Beginndatum
Kachelator
Peter Jerz
Meinst du den Mittelwert? Dazu gibt es in der STL den Algorithmus accumulate im <numeric>-Header. Du müsstet das Resultat dann nur noch durch die Anzahl der aufsummierten Elemente teilen.
Eine andere Möglichkeit wäre es, die Elemente von Hand in einer for-Schleife aufzusummieren und dann zu teilen. Dass meintest du vermutlich mit der IF-Schleife, oder verstehe ich dich falsch?
Eine andere Möglichkeit wäre es, die Elemente von Hand in einer for-Schleife aufzusummieren und dann zu teilen. Dass meintest du vermutlich mit der IF-Schleife, oder verstehe ich dich falsch?
Nein ich meine den Median, so wie ich es geschrieben habe.
Median wird wie folgt berechnet.
Voraussetzung: sortierte Zahlenwerte
1.a) Anzahl aller Elemente ist gerade: Median ist die Zahl an der Stelle ((n / 2) + ((n + 1) / 2) / 2
1.b) Anzahl aller Elemente ist ungerade: Median ist die Zahl an der Stelle (n / 2)
Bei 3 Zahlen wäre der Median die mittlere Zahl.
Bsp:
3, 7, 13 -> Median ist 7.
Trotzdem Danke
Median wird wie folgt berechnet.
Voraussetzung: sortierte Zahlenwerte
1.a) Anzahl aller Elemente ist gerade: Median ist die Zahl an der Stelle ((n / 2) + ((n + 1) / 2) / 2
1.b) Anzahl aller Elemente ist ungerade: Median ist die Zahl an der Stelle (n / 2)
Bei 3 Zahlen wäre der Median die mittlere Zahl.
Bsp:
3, 7, 13 -> Median ist 7.
Trotzdem Danke
Kachelator
Peter Jerz
Okay, da habe ich dich falsch verstanden. Du kannst aber dennoch die STL-Algorithmen verwenden, um beispielsweise eine Sequenz zu sortieren und dann das "mittlere" Element zu finden.
Würde dir das weiterhelfen? Na ja, so knifflig ist das auch ohne STlL ja nicht.
Würde dir das weiterhelfen? Na ja, so knifflig ist das auch ohne STlL ja nicht.
Stimmt schon, dass das nicht knifflig ist.
Es geht aber darum ein Programm zu schreiben das auf verschiedene Arten den QuickSort durchführt. Unter anderem soll er als Pivot den Median nehmen. Mir geht es eben nur darum diese ganzen Vergleiche auf ein minimum zu reduzieren um die WC-Komplexität gering zu halten.
Es geht aber darum ein Programm zu schreiben das auf verschiedene Arten den QuickSort durchführt. Unter anderem soll er als Pivot den Median nehmen. Mir geht es eben nur darum diese ganzen Vergleiche auf ein minimum zu reduzieren um die WC-Komplexität gering zu halten.
Thomas Darimont
Erfahrenes Mitglied
Hallo!
Um den Median einer Zahlenfolge zu bestimmen darf man nicht sortieren...
wir wollen ja gerade den Wert dieser Zahlenfolge der in Ungeordneten Reihenfolge (so wie die Werte eben reingekommen sind) in der "Mitte" im Sinne der Reihenfolge (nicht der Geordneten Reihenfolge) befindet. Den Median erhält man nach dem folgenden Ermittlungsschema:
Bsp.
Ungerade Anzahl:
Folge A = 4 2 8 7 0 1 3
Hier ist der Median: -> A((n+1) / 2) -> 7
Gerade Folge:
Folge A = 4 9 8 1 2 2 3 9
Hier ist der Median: -> (A(n/2) + A(n/2+1))/2 -> 1,5
Gruß Tom
Um den Median einer Zahlenfolge zu bestimmen darf man nicht sortieren...
wir wollen ja gerade den Wert dieser Zahlenfolge der in Ungeordneten Reihenfolge (so wie die Werte eben reingekommen sind) in der "Mitte" im Sinne der Reihenfolge (nicht der Geordneten Reihenfolge) befindet. Den Median erhält man nach dem folgenden Ermittlungsschema:
Bsp.
Ungerade Anzahl:
Folge A = 4 2 8 7 0 1 3
Hier ist der Median: -> A((n+1) / 2) -> 7
Gerade Folge:
Folge A = 4 9 8 1 2 2 3 9
Hier ist der Median: -> (A(n/2) + A(n/2+1))/2 -> 1,5
Gruß Tom
Hi
@Tom
Das ist AFAIK nicht korrekt. Der Median bezieht sich auf den mittleren Wert einer sortierten Folge. Er wird nicht nur in der Statistik, sondern auch gern in der Bildvorverarbeitung (BVV) benutzt, da sich mit ihm ein nichtlinearer Filter konstruiren lässt.
Zum Median siehe:
http://de.wikipedia.org/wiki/Median
@Romsel
Den Pivot über den Median zu nehmen ist doppelt gemoppelt, da das Array dazu bereits sortiert ist. Du kannst aber den Pivot bestimmen, in dem du das Array mit den Werten einmal abfährst und den kleinsten Wert raus suchst.
Empfehlen kann ich hierzu "Algorithmen und Datenstrukturen" von Herbert Kopp.
Siehe:
http://gd.tuwien.ac.at/books/skript...grotithmen_und_Datenstrukturen_001_g_198p.pdf
@Kachelator
Die STL ist ja man eine feine Sache, aber zum sortieren überhaupt nicht geeignet. Viel zu viel Overhead.
Gruss TB
@Tom
Das ist AFAIK nicht korrekt. Der Median bezieht sich auf den mittleren Wert einer sortierten Folge. Er wird nicht nur in der Statistik, sondern auch gern in der Bildvorverarbeitung (BVV) benutzt, da sich mit ihm ein nichtlinearer Filter konstruiren lässt.
Zum Median siehe:
http://de.wikipedia.org/wiki/Median
@Romsel
Den Pivot über den Median zu nehmen ist doppelt gemoppelt, da das Array dazu bereits sortiert ist. Du kannst aber den Pivot bestimmen, in dem du das Array mit den Werten einmal abfährst und den kleinsten Wert raus suchst.
Empfehlen kann ich hierzu "Algorithmen und Datenstrukturen" von Herbert Kopp.
Siehe:
http://gd.tuwien.ac.at/books/skript...grotithmen_und_Datenstrukturen_001_g_198p.pdf
@Kachelator
Die STL ist ja man eine feine Sache, aber zum sortieren überhaupt nicht geeignet. Viel zu viel Overhead.
Gruss TB
Kachelator
Peter Jerz
Hört, hört...TakaBo hat gesagt.:
Thomas Darimont
Erfahrenes Mitglied
Hallo!
@Takabo
du hast recht... schande über mein Haupt... aber ansonsten stimmen "meine" Rechenvorschriften ;-)
Gruß Tom
@Takabo
du hast recht... schande über mein Haupt... aber ansonsten stimmen "meine" Rechenvorschriften ;-)
Gruß Tom
