ub60 - Fr 19.12.08 12:14
Titel: Timingproblem bei Selectionsort
Hallo Leute,
beim Test von Selectionsort ist mir ein Problem bei der Messung der Sortierzeit aufgefallen.
Der eigentlich korrekte Quelltext:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| procedure TSort.SortiereSelectionSort;
var i, j, PosMaximum : Integer;
begin
for i:=FAnzahl downto 2 do
begin
PosMaximum:=1;
for j:=2 to i do
if FSortArray[j]>FSortArray[PosMaximum]
then PosMaximum:=j;
Tausche(i,PosMaximum);
end;
end; |
liefert eine um ca. 5 Prozent schlechtere Sortierzeit als der zweite Quelltext, der einen Schleifendurchlauf mehr durchführt, als benötigt:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
| procedure TSort.SortiereSelectionSort3;
var i, j, PosMaximum : Integer;
begin
for i:=FAnzahl downto 2 do
begin
PosMaximum:=1;
for j:=1 to i do
if FSortArray[j]>FSortArray[PosMaximum]
then PosMaximum:=j;
Tausche(i,PosMaximum);
end;
end; |
Hat jemand eine Erklärung, warum bei mehr Durchläufen (Quelltext 2) die Sortierzeit länger wird?
Ach so, Messfehler sollten ausgeschlossen sein, da ich jeden Wert mit ca. 500 Sortieraufrufen gemittelt habe.
ub60