Algo gesucht: Größte und kleinste Element einer Menge?
-
Hello Forum,
ich suche einen Algo für dieses Problem:
Array mit Integern. Es soll das größte und kleinste Element ermittelt werden. Es dürfen nur 1,5 mal so viele Vergleichsoperationen durchgeführt werden wie Elemente im Array sind.
Man könnte paarweise vergleichen: Im ersten Durchgang das größte Element suchen, im zweiten das kleinste. Wenn man durch Vergleichen ein neues Extrema gefunden hat, kann man das alte "wegwerfen", weil es nachweislich in der Menge sowohl noch ein größeres als auch ein kleineres Element geben muß. Es läßt sich aber immer wieder eine Menge konstruieren die knapp 2*Arraygröße viele Vergleiche benötigt...
Es muß da irgendeine bessere Idee geben. Habt Ihr eine Idee?
-
das klingt nach sortieren mit einem O(n log n) algorithmus. damit machst du dir evtl mehr arbeit als die aufgabe verlangt, abes es sollte in die 1.5n vergleiche passen.
-
Jeweils zwei Elemente des Arrays miteinander vergleichen, dann den größeren von beiden mit dem bisherigen Maximum vergleichen, den kleineren mit dem bisherigen Minimum. Danach die nächsten zwei Elemente usw.
@c.rackwitz: Dann darf aber log n höchstens 3/2 sein. Das passt nicht.
-
@c.rackwitz: Es ist keine O-Notationsaufgabe. Die 1,5 * Arraygrößengrenze ist hart.
@MFK: Genau das ist es. Danke
-
Selbst mit O-Notation benötigt man zum Sortieren O(n log n) Vergleiche. Und das ist nicht linear.
-
Hast Recht. Aber die Konstante wäre variabel und mit 2*Arraygröße würde ich die Aufgabe locker hinkriegen...
-
[quark, kann geloescht werden]
-
weiß jetzt nciht genau aber boost biete meiner meinung nach
boost::minmax an. Wie das ist und welche komlexität es hat weiß ich nciht
-
Also ich bin nicht zu 100% sicher, ob meine Argumentation stimmt, denn ich bin nicht versiert genug in der Materie, also korrigiert mich bitte wenn ich Mist schreibe^^. Meine Idee wäre folgende:
1. Ein bool-Array mit gleichvielen Elementen wie das int-Array anlegen.
2. Immer 2 Werte des int Arrays miteinander vergleichen also 0 mit 1,2 mit 3 usw.
Damit haben wir Arraygröße/2 Vergleichsoperationen.
3. Im bool-Array jeweils die Werte true setzen, deren Zahlen größer waren (Wenn also 24 größer war als 25, dann boolArray[24]=true)
4. Danach den Vorgang wiederholen, aber nur noch die Zahlen vergleichen, die als true gekennzeichnet sind.
Das sollten dann Arraygröße/4 Vergleiche sein.
Dann das ganze nochmal und solange, bis nur noch eine Zahl übrig ist. Und dann analog für das Minimum.Meinen Mathekenntnissen nach ist x/2 + x/4 + x/8 + x/16 + ... = x.
Hoffe das hilft, phyll
-
Damit hast Du dann 2n-2 Vergleiche. Wie es richtig geht, hat MFK ja schon beschrieben.
-
Denkfehler, ich dachte man dürfte für Minimum und Maximum jeweils 1,5 mal so viele Vergleiche machen...
-
An sich hat Phyll schon Recht. Es wären auch bei ihm 1,5*n Vergleiche. Denn wenn er das Minimum errechnet muß er die x/2 Vergleiche nicht nochmal durchführen. Er kann das bool Array aus der Max Berechnung weiterverwenden.
Wie das wiederholte Anlegen des Arrays zu bewerten wäre, da bin ich mir nicht sicher. Allerdings war nur die maximale Anzahl der Vergleichsoperationen in der Aufgabenstellung vorgegeben...
@Maxi: Die Aufgabe war aus TheoretischeInformatik III. Es würde mich aber schon sehr reizen auf boost::minmax zu verweisen *g* (Es soll nur ein PseudoCode Programm auf Papier abgegeben werden.)