Mehrere Variablen vergleichen

[gammatester]

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;