BubbleSort1 vs. BubbleSort2

[Deep-Sea]

Hier mal ein Screenshot aus meiner Testsoftware:
Sort.png
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.)

[Uwe Raabe]

Zitat von Deep-Sea:

Der von Uwe Raabe gepostete Quelltext ist jedoch KEIN InsertSort, da er die innere Schleife immer komplett durchläuft, genau wie BubbleSort.

Das hast du vollkommen richtig erkannt (daher auch meine Bemerkung "einfach aber langsam"). Natürlich kann man da noch einiges optimieren. Z.B. den Vergleichswert AList[J] einmal vor der Schleife in eine lokale Variable packen. Bei einem Exchange würde er für den nächsten Vergleich wieder herangezogen und ohne Exchange ist die Schleife eh am Ende.

Wenn man das Speicherlayout des Arrays kennt, kann man auch die Schleife solange ohne Exchange durchlaufen bis man den Einfügepunkt gefunden hat und dann die entsprechenden Elemente per Move nach hinten schieben. Das entspricht dann schon eher der Metapher des "Karteneinsorierens" nach dem der InsertSort ja angeblich seinen Namen hat.

[Deep-Sea]

Zitat von Uwe Raabe:

Z.B. den Vergleichswert AList[J] einmal vor der Schleife in eine lokale Variable packen. [...]

Ich wollte letztens auch etwas optimieren, bei dem ich einen redundanten Zugriff auf ein Array-Eintrag eliminieren wollte. Ebenfalls mit lokaler Variable. Und was passierte? Es war langsamer! Delphi schien an der Stelle schon perfekt optimiert zu haben ^^

Zitat von Uwe Raabe:

[...] die entsprechenden Elemente per Move nach hinten schieben. [...]

Ich hab aus Spaß einen Sortieralgo "entwickelt", der auch im Testprogramm ist. Dieser nutzt eine leicht modifizierte binäre Suche um die richtige Position zu finden und verschiebt dann ebenfalls. Aber verschieben ist i.d.R. sehr zeitaufwendig - außer bei verketteten Listen ...

[Bjoerk]

Neben dem, was Gargoyl schon ausgeführt hat:

Bei Listen mit vielen unterschiedlichen Elementen ist Variante 1 geringfügig schneller als Variante 2, bei Listen mit vielen gleichen Elementen hat Bubbelsort2 seinen Schwachpunkt, da ist Variante1 ca. Faktor 2 schneller.

Wer ein langweiliges Wochenende vor sich hat, hier etwas Code zum spielen:

Schönes Wochenende
Thomas

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TVek = array of integer;

  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    procedure FormCreate(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

var
  A, B, C, D: TVek;


procedure BubbleSort1 (var A: TVek);
var
  I, J, T: integer;
begin
  for I:= 0 to Length(A)-2 do
    for J:= I+1 to Length(A)-1 do
      if A[I] > A[J] then
      begin
        T:= A[I];
        A[I]:= A[J];
        A[J]:= T;
      end;
end;


procedure BubbleSort2 (var A: TVek);
var
  i, LastChecked, temp: Integer;
  done: Boolean;
begin
  LastChecked := 0;
  repeat
    done := True;
    inc(LastChecked);
    for i := Low(A) to High(A) - LastChecked do
    begin
      if A[i] > A[i + 1] then
      begin
        temp := A[i];
        A[i] := A[i + 1];
        A[i + 1] := temp;
        done := False;
      end;
    end;
  until done;
end;


procedure InsertSort (var A: TVek);
var
  I, J, T: Integer;
begin
  For I := 1 to Length(A)-1 do
  begin
    J := I;
    While ((J > 0) and (A[J-1] > A[J])) do
    begin
      T:= A[J-1];
      A[J-1]:= A[J];
      A[J]:= T;
      Dec(J);
    end;
  end;
end;


procedure QuickSort (var A: TVek; L, R: Integer);
var
  I, J, P, T: Integer;
begin
  repeat
    I := L;
    J := R;
    P := A[(L + R) shr 1];
    repeat
      while A[I] < P do Inc(I);
      while A[J] > P do Dec(J);
      if I <= J then
      begin
        T := A[I];
        A[I] := A[J];
        A[J] := T;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then QuickSort(A, L, J);
    L := I;
  until I >= R;
end;


function ZufallsZahl(const Von, Bis: integer): integer;
begin
  Result:= Random(Succ(Bis-Von))+Von;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
  I: integer;
  fTime: Cardinal;
begin
  for I:= 0 to Length(A)-1 do
  begin
    A[I]:= ZufallsZahl(0, 99);
    B[I]:= A[I];
    C[I]:= A[I];
    D[I]:= A[I];
  end;

  fTime:= GetTickCount;
  BubbleSort1(A);
  Label1.Caption:= 'BubbleSort1: '+IntToStr(GetTickCount-fTime)+' ms';

  fTime:= GetTickCount;
  BubbleSort2(B);
  Label2.Caption:= 'BubbleSort2: '+IntToStr(GetTickCount-fTime)+' ms';

  fTime:= GetTickCount;
  InsertSort(C);
  Label3.Caption:= 'InsertSort: '+IntToStr(GetTickCount-fTime)+' ms';

  fTime:= GetTickCount;
  QuickSort(D, 0, Length(D)-1);
  Label4.Caption:= 'QuickSort: '+IntToStr(GetTickCount-fTime)+' ms';
end;


procedure TForm1.FormCreate(Sender: TObject);
begin
  Randomize;
  SetLength(A, 20000);
  SetLength(B, 20000);
  SetLength(C, 20000);
  SetLength(D, 20000);
end;


procedure TForm1.FormDestroy(Sender: TObject);
begin
  SetLength(A, 0);
  SetLength(B, 0);
  SetLength(C, 0);
  SetLength(D, 0);
end;


end.

[ldelafosse]

[QUOTE=Deep-Sea;1109588]Hier mal ein Screenshot aus meiner Testsoftware:
Anhang 34559
Mein Code ist ggf. etwas verwirrend, er ist halt aus meiner Testsoftware ...
QUOTE]

Is your Testsoftaware available?

It's look pretty good, and to have a lot of informations on each sort type of algorithm.