Forum: Object-Pascal / Delphi-Language
by gammatester,
24. Mai 2010
Da wird nix länger dauern (außer für sehr kleine Arrays). Mit der folgenden Initialisierung (beachte umgekehrte Sortierung)
setlength(arr, NMAX);
j := high(arr);
for i:=0 to j-1 do arr := -i;
arr := arr;
erhalte ich für NMAX:
20000 mit 'optimierter' Schleife 721 ms
20000 mit Quicksort 0 ms
Forum: Object-Pascal / Delphi-Language
by gammatester,
24. Mai 2010
Schon klar. Wie schon gesagt, wäre eine separate Funktion mit einem exit oder ein goto noch schneller.
Allerdings ist wohl selbst dann im schlimmsten Fall immer noch eine quadratische Laufzeit erforderlich. Mit einem n*log(n) Sortierverfahren mit anschließendem linearen Vergleich oder eine Hashliste hätte man eine bessere Worst-case-Laufzeit.
Forum: Object-Pascal / Delphi-Language
by gammatester,
24. Mai 2010
Aber nur, wenn Du es vernünftig programmiert hättest! Um Deinen Fehler zu sehen, teste mal Deinen Code mit folgenden Vorgaben: setlength(arr, 10000000);
for i:=0 to high(arr) do arr := i;
arr := 1;
In der Zwischenzeit hier die Erklärung: Dein angeblich fast optimaler Code verläßt via break verläßt nämlich nur die innere for-Schleife, und die äußere Schleif wird immer wieder durchlaufen, auch...
