Hier mal ein Screenshot aus meiner Testsoftware:
Die hier gezeigte BubbleSort-Implementation ist die zweite, also die schnellere.
Die Ausführungszeit sollte man hier mal vernachlässigen, die ist nur mit GetTickCount gemessen und bei der kurzen Zeit natürlich nicht aussagekräftig.
Interessant ist eher "Zwei Elemente verglichen", hier ist InsertSort im Durchschnitt eben doppelt so schnell wie BubbleSort - und dafür ist der Code nicht komplizierter.
Der von Uwe Raabe gepostete Quelltext ist jedoch KEIN InsertSort, da er die innere Schleife immer komplett durchläuft, genau wie BubbleSort.
Mein Code ist ggf. etwas verwirrend, er ist halt aus meiner Testsoftware:
Delphi-Quellcode:
class procedure TCtInsertSort.Sort(AList: TCtSortTestList; ASorter: TCtSort);
var
I, J: Integer;
begin
For I := 1
to AList.Count - 1
do
begin
J := I;
While (J > 0)
and ASorter.DoCompare(AList[J - 1], AList[J])
do
begin
AList.Exchange(J - 1, J);
Dec(J);
end;
end;
end;
Wie man hier sieht, wird die innere Schleife abgebrochen, sobald ASorter.DoCompare einmal
false zurück liefert. (ASorter.DoCompare liefert false zurück, wenn das erste Element kleiner-gleich dem zweiten ist.)