Wie Eingaben vergleichen bzw. den kleinsten Wert finden

[Leno]

-

 

[Lesco]

also ich würde es so machen:
Zahlen[] sei das Array an Zufallszahlen, aus dem du das Minimum finden willst.

int min=0;
for(int i=0;i<Zahlen.length();++i) {
   if(Zahlen[i] < Zahlen[min]) 
      min=i;
}

Dann hast du in der Variable min den Index des kleinsten Elements.
btw: ggf. "Zahlen.length()" mit der Größe des Arrays ersetzen

 

[Leno]

-

 

[MTS]

evtl. kannst du die niedrigste Zahl doch schon beim erstellen der Zufallszahlen mitprotokollieren ... also jede neue zahl mit dem bisherigem minimum vergleichen.

Weniger vergleiche sollte eh nicht gehen ... ob es in Bezug auf die Vertauschungen effizient ist, kann ich dir nicht verprechen ;-)

 

[Xanti]

...oder man definiert als kleinste Zufallszahl "0", dann gehts ohne vergleichen

 

[Lesco]

Danke.

Aber bin grad am Überlegen ob ich nicht doch eine eigene Routine schreib, da das Programm später mal in Richtung 10^3 oder 10^4 Zahlen sortieren können soll. Ich denke da ist dann was effektives gefragt.

Suche grad was zu Introsort ;-)

Cheers Leno

Wenn du es komplett sortieren und nicht nur das Minimum finden willst, dürfte afaik Quicksort die schnellste Lösung sein.

 

[pinky]

Wenn du es komplett sortieren und nicht nur das Minimum finden willst, dürfte afaik Quicksort die schnellste Lösung sein.

Der Name ist nicht unbedingt Programm.
Mit einem Heapsort sollte man bessere Ergebnisse erziehlen können.

Wenn man aber nur das kleinste Element sucht ist es nicht sinnvoll erst das ganze Feld zu sortieren.

 

[rikola]

Falls Du C++ programmierst, wuerde ich die Zahlen in einem vector speichern und std::sort bzw. std::min_element aus <algorithm> benutzen.
In C wuerde ich einfach durchsuchen, schneller geht es nicht, da Du ja ohnehin jeden Werte einmal abfragen musst. Falls Du sortieren willst, gibt es in stdlib.h zumindest ein qsort.

 

[Leno]

-

 

[cremi]

verwende doch einfach qsort

 

[liquidnight]

ich hab schon ne weile kein c++ mehr programmiert drum meine frage dazu: in java steckt man die zahlen in einen Integer oder Long und die steckt man dann in ein Treeset. das sortiert beim eintüten gleich und am Ende nimmt man sich einfach das erste Element raus. Gibts da ne vergleichbare Collection-Klasse für C++ ?

bei den boost-libraries vielleicht ?

 

[nic]

In Java gibts genauso Quicksort und co, da brauchst du eigentlich nicht erst das Ganze in nen Tree zu stecken wenn du den spaeter nicht sowieso brauchst...

 

[cremi]

also ich würde es so machen:
Zahlen[] sei das Array an Zufallszahlen, aus dem du das Minimum finden willst.

int min=0;
for(int i=0;i<Zahlen.length();++i) {
   if(Zahlen[i] < Zahlen[min]) 
      min=i;
}

Dann hast du in der Variable min den Index des kleinsten Elements.
btw: ggf. "Zahlen.length()" mit der Größe des Arrays ersetzen

so einfach gehts doch!!!
warum bäume und collecton klassen - ist doch viel zu kompliziert
und schnell genug ist das sicherlich für nur 10^5 werrte.

doch falls es kompliziert sein soll - warum schreibst du die werte nicht in eine datenbank (am besten oracle) und holst dir dann den kleinsten wert:

SELECT MIN(value) as "most_complicated_solution" FROM random_numbers;

na ja, spass bei seite - ich würds so wie oben machen

 

[pinky]

so einfach gehts doch!!!
warum bäume und collecton klassen - ist doch viel zu kompliziert
und schnell genug ist das sicherlich für nur 10^5 werrte.

Es ist nicht nur schnell genug, sondern es ist _das_ schnellste. Jeder Sortieralgorithmus (egal ob irgendwelche Baumstrukturen oder so, alle sind im mittel schlechter wie O(n) ) Es gibt nichts schnelleres/einfacheres wie jedes Element genau einmal an zu sehen (evtl. kann man auch schon früher abbrechen wenn man die untergrenze der möglichen Zahlen kennt).

Wenn die Zahlen im Programmlauf erzeugt oder eingelesen werden und man weiß, dass man nachher garantiert das kleinste Element braucht, dann empfiehlt es sich natürlich diese direkt hier schon zu ermitteln, da ich beim einlesen/erzeugen eh schon jede Zahl in der Hand habe.

Sortieren lohnt sich nur, wenn ich irgendwann im Programmlauf wirklich die vollkommen sortierte Menge brauche!

 

[Xanti]

Angenommen, man will 1000 Zufallszahlen zwischen 0 und 1 erstellen sowie die kleinste Zahl davon bestimmen. Dann kann man 500 Zufallszahlen zwischen 0 und 0.5 sowie 500 Zahlen zwischen 0.5 und 1 erstellen. Für die kleinste Zahl braucht man nur die ersten 500 Zahlen vergleichen (499 Vergleiche). Dies kann man noch verfeinern, also zum Beispiel 100 Zahlen zwischen 0 und 0.1 sowie 900 zwischen 0.1 und 1 (99 Vergleiche) usw...

Berücksichtigen muss man dann nur noch die Güte der Zufallszahlen bezüglich ihrer Verteilung.

Gruss, Phorus

edit: Bei Gleichverteilung sehe ich kein Problem.

edit2: Es kommt natürlich drauf an, was billiger ist: Vergleich oder Division zweier Zahlen

 

[pinky]

edit: Bei Gleichverteilung sehe ich kein Problem.

Das ist eben der Punkt. Bei einer 100%igen Gleichverteilung könntest du sogar nur die erste Zahl per Zufall bestimmen lassen und alle anderen gleichmäßig um diese Zahl herum verteilen.
Ich denke mal von Zufallszahlen erwartet man aber meistens doch etwas mehr Zufall und nicht, dass z.B. immer gleich viele Elemente unter 0.5 fallen und gleich viele über 0.5. Der Zufall sollte durchaus auch mal die Möglichkeit haben mehr Zahlen in den oberen oder in den unteren Bereich zu streuen.
Im schnitt sollte es bei vielen durchläufen dann natürlich schon ziemlich nahe an die Gleichverteilung ran kommen, damit man von einem guten Zufallsalgorithmus sprechen kann. Aber ein Zufallsalgorithmus der sich in jedem durchlauf an die Gleichverteilung hält halte ich in den meisten Fällen eher für unerwünscht.

 

[Xanti]

Richtige Zufallszahlen wirst Du nicht durch einen billigen Zufallszahlengenerator bekommen, die bekommt man nur, wenn man selber würfelt

Aber nach dem Gesetz der grossen Zahlen ist es wahrscheinlicher, dass man, je mehr Zahlen man wählt, auch wirklich ungefähr die Hälfte der Zufallszahlen zwischen 0 und 0.5 findet (bei Gleichverteilung).

Gruss, Phorus

 

[Leno]

-

 

[cremi]

Es ist nicht nur schnell genug, sondern es ist _das_ schnellste. Jeder Sortieralgorithmus (egal ob irgendwelche Baumstrukturen oder so, alle sind im mittel schlechter wie O(n) ) Es gibt nichts schnelleres/einfacheres wie jedes Element genau einmal an zu sehen (evtl. kann man auch schon früher abbrechen wenn man die untergrenze der möglichen Zahlen kennt).

wollte eigentlich das selbe aussagen - stimm dir voll zu