TIA Min Max mit Bubble Sort

[kiar]

Zuviel Werbung?
-> Hier kostenlos registrieren

Moin,

will aus einer Liste ( Array ) den kleinsten und den größten Wert ermitteln. Dies mache ich jetzt mit Bubble Sort.
Gibt es eine andere bzw. bessere Möglichkeit oder ist dies schon die beste(einfachste)?

Raik

 

[MasterOhh]

Willst du nur den kleinsten und größten Wert ermitteln oder das komplette Array sortieren?
Wenn es dir nur um das Minimum und Maximum geht, braucht du keinen Sortieralgorithmus.

Min um Max im Array kannst du in einem einzigen Durchgang ermitteln.

Min := Array[0]
Max := Array[0]

For i := 1 to 100 do

  if Array[i] < Min then
    Min := Array[i]
  end_if

  if Array[i] > Max then 
    Max := Array[i]
  end_if

end_for

Am Ende der Schleife enthält Min den kleinsten Wert im Array und Max den größten Wert.

 

[inspectorgadjet]

Zuviel Werbung?
-> Hier kostenlos registrieren

Naja, ich würde folgendes machen:

Pseudocode

min = max = element[1]

for i=2 to i=länge von element
If element < min then min= element
If element > max then max=element
end for

Somit sollte am Ende min die kleinste und max die größte Zahl. Laufzeit O statt O(n^2)

VL. reicht auch, dass du pro Zyklus nur ein element vergleichst. Kommt darauf an, wie oft du min/max berechnet werden muss.

Edit: zu langsam

 

[vollmi]

Die bessere Möglichkeit wäre, das Array einmal durchzugehen und den ersten Wert abzulegen und dann immer auf grösser oder kleiner (je nach Zwischenspeicher) zu vergleichen und entsprechend abzulegen.

z.B. so.

maxspeicher := ARRAY1[0];
   FOR index := 0 TO 100 BY 1 DO
        IF ARRAY1[index] > maxspeicher THEN
            maxspeicher := ARRAY1[index];
        END_IF;        
    END_FOR;
   
minspeicher := ARRAY1[0];
   FOR index := 0 TO 100 BY 1 DO
        IF ARRAY1[index] < minspeicher THEN
            minspeicher := ARRAY1[index];
        END_IF;        
    END_FOR;

mfG René

 

[hucki]

Vollmis Beispiel ist voll funktionsfähig und super übersichtlich und trotzdem würde ich für mich 2 Sachen bemängeln:
1. Dem Speicher wird als erstes der Inhalt des 1. Feldelementes zugewiesen. In der FOR-Schleife wird dann trotzdem nochmal dieses 1. Element geprüft, ob es kleiner/größer als der Speicher ist. M.M.n. (und nach der von vollmis Vorrednern) überflüßig. Es genügt, wenn die FOR-Schleife beim 2. Element des Arrays beginnt.
2. Beide FOR-Schleifen in vollmis Code durchlaufen den gleichen Wertebereich, deshalb würde ich auch hier (wie seine Vorredner) beide Abfragen in eine Schleife packen, um mir einen Durchlauf einzusparen.


Mit IF..THEN abfragen kannst Du Dir das Minimum und Maximum einfach selber ausfiltern, wie Dir die Beispiele oben zeigen.
TIA bietet Dir aber auch fertige Funktionen und da Du Dich ja mit allem vertraut machen möchtest:

#Minimum:= #TestArray[0];
#Maximum:= #TestArray[0];

FOR i := 1 TO 100 BY 1 DO

  #Minimum := MIN( IN1:= #Minimum, IN2:= #TestArray[i] );
  #Maximum := MAX( IN1:= #Maximum, IN2:= #TestArray[i] );

END_FOR;

Zusätzliche Hinweise, da ich nicht weiß, wie Du das bis dato handhabst:
Auch wenn TIA Dir erlaubt, Funktionsnamen als Variablennamen zu verwenden, würde ich mir das möglichst nicht angewöhnen.
Außerdem würde ich gerade während der "Schulzeit" die Funktionen, wie FOR-Schleifen, immer mit allen Optionen angeben, auch wenn man das bei Standards, wie z.B. "BY 1", nicht unbedingt machen muss.


PS:
Bei der Gelegenheit könntest Du auch testen, ob es vlt. Geschwindigkeitsvor- oder -nachteile bringt, mehrere Elemente auf einmal zu prüfen (wobei 100 Arrayelemente wahrscheinlich etwas wenig für diesen Test sind):

#Minimum:= #TestArray[0];
#Maximum:= #TestArray[0];

FOR i := 1 TO 96 BY 5 DO

  #Minimum := MIN( IN1:= #Minimum, IN2:= #TestArray[i], IN3:= #TestArray[i + 1], IN4:= #TestArray[i + 2], IN5:= #TestArray[i + 3], IN6:= #TestArray[i + 4] );
  #Maximum := MAX( IN1:= #Maximum, IN2:= #TestArray[i], IN3:= #TestArray[i + 1], IN4:= #TestArray[i + 2], IN5:= #TestArray[i + 3], IN6:= #TestArray[i + 4] );

END_FOR;

 

[kiar]

Zuviel Werbung?
-> Hier kostenlos registrieren

Moin,

Ich möchte mich bei Euch 4 bedanken.

@hucki: das es da schon eine fertige Funktion gibt hatte ich noch gar nicht auf dem Schirm.
Ich habe mich jetzt für die Variante von MasterOhh entschieden, ist für mich übersichtlicher.

Raik

 

[franzz]

Es gibt durchaus noch bessere Lösungen (je nachdem, was man unter "besser" versteht).

Das Array einmal durchzugehen ist sicher am einfachsten, braucht aber O Zeit (also bei doppelt so langem Array doppelt so lang). Eine Alternative wäre eine "priority queue", damit ist das in O(log n) möglich (also bei sehr langen Arrays deutlich schneller).

Ob sich der Aufwand lohnt, weiß ich natürlich nicht...