aus einem Array die kleinste Zahl herausfinden

[gangs-taas]

danke
ich habs mit ner schleife gelöst

[himitsu]

zum Thema sortuert = schneller

wenn das Array vorher schon sortiert ist, dann isses natürlich schneller

[alzaimar]

Zitat von himitsu:

wenn das Array vorher schon sortiert ist, dann isses natürlich schneller

Woher weiss man das?

[Meflin]

Zitat von alzaimar:

Woher weiss man das?

Indem man es beim Einfügen schon sortiert hält

Aber genug der Theorie. Gesetz dem äußerst unwahrscheinlichen Fall, dass man tatsächlich nur ein allereinziges Mal das Minimum haben will, ist lineare Suche wirklich das Beste

[alzaimar]

Zitat von Meflin:

Zitat von alzaimar:

Woher weiss man das?

Indem man es beim Einfügen schon sortiert hält

Das ist dann auch langsamer als mal eben in einem unsortierten Array zu suchen

Zitat von Meflin:

Gesetz dem äußerst unwahrscheinlichen Fall, dass man tatsächlich nur ein allereinziges Mal das Minimum haben will

Wieso sollte ich öfter das Minimum eines Arrays ermitteln? Ändern tut es sich doch eh nicht

Nun zur Theorie:
Wenn ich eine listenartige Datenstruktur inklusive Kenntnis des kleinsten/größten Elements benötige, werde ich meine Basisstruktur u.a. danach aussuchen, ob ich die Elemente sortiert benötige. Wenn nicht, und Löschoperationen selten sind, dürfte eine unsortierte Liste eine gute Wahl darstellen. Ansonsten empfehle ich eine Skiplist, die hier im Gegensatz zu einer sortierten Liste stets optimale Ergebnisse liefert. So sind so gut wie alle Operationen näherungsweise O(1), wohingegen eine sortierte Liste beim Einfügen und Löschen einen Aufwand O(n) und beim Suchen O(log n) aufweist. Nicht besonders, wenn Du mich fragst.

[Namenloser]

Zitat von Meflin:

Zitat von alzaimar:

Woher weiss man das?

Indem man es beim Einfügen schon sortiert hält

Kommt aber darauf an, wie man das macht. Wenn man quasi Insertion-Sort verwendet, ist es wahrscheinlich langsamer, weil die Elemente imemr wieder verschoben werden müssen. Und natürlich wird auch dabei das Array durchgescannt, mit dem Unterschied dass man hier eine binäre Suche verwenden kann, was aber nur bei größeren Mengen an Daten einen Geschwindigkeitsvorteil bringt.

[Meflin]

Zitat von NamenLozer:

Wenn man quasi Insertion-Sort verwendet, ist es wahrscheinlich langsamer

Wieso auch nicht gleich BogoSort

[himitsu]

Und wenn sich die Werte im Array ändern?

Dann gibt es für's Hinzufügen 2 Wege

- entweder sortiert hinzufügen
- oder beim Hinzufügen direkt mit den zwischengespeicherten Min- und Max-Werten vergleichen und diese so aktuell halten

[Wolfgang Mix]

Ergänzung zu Post 8:

Hier eine bessere Testvarinte:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
 var zahl : array[1..1000] of integer;
  i,min,merker:integer;
begin
  randomize;
   for i:= 1 to 1000 do
   begin
     zahl[i]:=random(10000)+1;
   end;
   min:=1000;
   for i:= 1 to 1000 do
   begin
     if zahl[i] < min then
     begin
       min:=zahl[i];
       merker:=i;
     end;
   end;
   edit1.Text:=IntToStr(min);
   edit2.Text:=IntToStr(merker);
end;

Gruß

Wolfgang

[alzaimar]

Zitat von Wolfgang Mix:

Hier eine bessere Testvarinte:

Und hier eine kürzere Testvariante:
KleinsterWert := Math.MinIntValue(zahlArray);