BubbleSort1 vs. BubbleSort2

[Bjoerk]

Hallo Gemeinde,

wir hatten eben eine Diskussion darüber, welcher der beiden Algorithmen wohl übersichtlicher und/ oder schneller ist (mal davon abgesehen, daß beide stink langsam sind). Mich würde eure Meinung interessieren.

Liebe Grüße
Thomas

Delphi-Quellcode:

type
  TVek = array of double;

procedure BubbleSort1 (var A: TVek);
var
  I, J: integer;
  T: double;
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: Integer;
  temp: double;
  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;

[himitsu]

Machen die Beiden nicht das Selbe Gleiche?
[edit] @Gargoyl: stümmt, hab das done übersehn

Nur einer jeweils von oben nach unten und der Andere andersrum.

PS: Wenn ihr wissen wollt, wer schneller ist, dann meßt doch einfach nach?

stellt eine zu sortierende Menge zusammen, und laßt beide die selben Daten sotrtieren ... dan natürlich mehrmals und dann den Mittelwert bilden oder einfach die Gesamtzeiten vergleichen.

[Uwe Raabe]

Wenn es hier um "einfach aber langsam" geht, hab ich auch noch einen

Delphi-Quellcode:

procedure InsertSort (var A: TVek);
var
  I, J: integer;
  T: double;
begin
  for I:= 1 to Length(A) - 1 do
    for J:= I downto 1 do
      if A[J - 1] > A[J] then
      begin
        T:= A[I];
        A[I]:= A[J];
        A[J]:= T;
      end;
end;

Aber unter XE ist das ja alles nicht mehr nötig:

Delphi-Quellcode:

uses
  Generics.Collections;
...  
TArray.Sort<Double>(A);

[Gargoyl]

Also Bubblesort1 hat immer eine konstante Laufzeit, egal ob die Liste bereits sortiert ist oder nicht. Also best case = average case = worst case. Und die Laufzeit ist immer in O(n²).

Bubblesort2 durchläuft bei einer bereits sortierten Liste das ganze nur einmal. Also im best case liegt die Laufzeit in O(n). Wenn die Liste komplett falsch herum (absteigend statt aufsteigend) sortiert ist dann ist die Laufzeit wieder in O(n²). Und im average case liegt sie dann irgendwo dazwischen.

Im worst case sind also beide gleich. Im best case und average case ist Variante 2 schneller.

[jfheins]

Zitat von Bjoerk:

Hallo Gemeinde,

wir hatten eben eine Diskussion darüber, welcher der beiden Algorithmen wohl übersichtlicher und/ oder schneller ist (mal davon abgesehen, daß beide stink langsam sind). Mich würde eure Meinung interessieren.

Liebe Grüße
Thomas

Um auch zum ersten Punkt was beizutragen: Übersichtlicher finde ich klar den ersten Code. Hat weniger Zeilen.

[Deep-Sea]

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

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

[Woyzeck]

Zitat von Gargoyl:

Also Bubblesort1 hat immer eine konstante Laufzeit, egal ob die Liste bereits sortiert ist oder nicht. Also best case = average case = worst case. Und die Laufzeit ist immer in O(n²).[...]

konstante Laufzeit und O(n²)...


Mir ist klar was du meinst, aber der Begriff ist wohl falsch gewählt an der Stelle.