Zitat von
himitsu:
Diese Schleife (inkl. richtiger Abruchbedingung) sollte im Worst-Case bei n*(n-1)/2 liegen. :gruebel:
PS: Aha, du willst also alles mehrfach durchgehn? @gammatester
- sortieren mit n*log(n)
- und prüfen mit n-1
wird bestimmt länger dauern.
Da wird nix länger dauern (außer für sehr kleine Arrays). Mit der folgenden Initialisierung (beachte umgekehrte Sortierung)
Delphi-Quellcode:
setlength(arr, NMAX);
j := high(arr);
for i:=0 to j-1 do arr[i] := -i;
arr[j] := arr[j-1];
erhalte ich für NMAX:
Code:
20000 mit 'optimierter' Schleife 721 ms
20000 mit Quicksort 0 ms
1000000 mit Quicksort 220 ms
Den Wert für 1000000 mit 'optimierter' Schleife kannst Du ja mal bestimmen. Dabei ist der Ablauf mit Quicksort wie folgt:
Delphi-Quellcode:
Quicksort(...);
for i:=0 to high(arr)-1 do begin
if arr[i]=arr[i+1] then begin
doppelt := true;
break;
end;
end;