BubbleSort1 vs. BubbleSort2

[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.