aus einem Array die kleinste Zahl herausfinden

[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.