Stabiles Sortieren

[Amateurprofi]

Zitat von Zacherl:

Hatte das gleiche Problem und in der RTL leider nichts gefunden. Habe mir dann eine einfache BubbleSort Implementation in meine Array-Helper Klasse eingebaut:

Delphi-Quellcode:

class procedure TArrayHelper.Exchange<T>(var A: TArray<T>; Index1, Index2: Integer);
var
  Temp: T;
begin
  Temp := A[Index1];
  A[Index1] := A[Index2];
  A[Index2] := Temp;
end;

class procedure TArrayHelper.BubbleSort<T>(var A: TArray<T>; const Comparer: IComparer<T>);
var
  I: Integer;
  Done: Boolean;
begin
  repeat
    Done := true;
    for I := Low(A) to High(A) - 1 do
    begin
      if (Comparer.Compare(A[I], A[I + 1]) > 0) then
      begin
        Exchange<T>(A, I, I + 1);
        Done := false;
      end;
    end;
  until Done;
end;

Ist bei vielen Werten natürlich fürchterlich langsam. Wollte bei Gelegenheit mal MergeSort implementieren.

Ich verwende ein etwas anderes BubbleSort.
Hintergrund:
Nach dem Durchlauf der For ... Schleife steht das größte Element am Ende des Arrays.
Also muss beim nächsten Durchlauf das vorletzte Element nicht mehr mit dem letzten Element verglichen werden.
Das verringert die Anzahl der zu vergleichenden Elemente bei jedem Durchlauf um 1.

Delphi-Quellcode:

class procedure TArrayHelper.BubbleSort<T>(var A: TArray<T>; const Comparer: IComparer<T>);
var
  I,Last: Integer;
  Done: Boolean;
begin
  Last:=High(A); 
  repeat
    Dec(Last) 
    Done := true;
    for I := Low(A) to Last do
    begin
      if (Comparer.Compare(A[I], A[I + 1]) > 0) then
      begin
        Exchange<T>(A, I, I + 1);
        Done := false;
      end;
    end;
  until Done;
end;

[Zacherl]

Zitat von Amateurprofi:

Ich verwende ein etwas anderes BubbleSort.
Hintergrund:
Nach dem Durchlauf der For ... Schleife steht das größte Element am Ende des Arrays.
Also muss beim nächsten Durchlauf das vorletzte Element nicht mehr mit dem letzten Element verglichen werden.
Das verringert die Anzahl der zu vergleichenden Elemente bei jedem Durchlauf um 1.

Guter Einwand Sollte dann aber am Anfang vermutlich Last := High(A) - 1 sein, sonst kracht es beim Zugriff auf A[I + 1] .

[Amateurprofi]

Zitat von Zacherl:

Zitat von Amateurprofi:

Ich verwende ein etwas anderes BubbleSort.
Hintergrund:
Nach dem Durchlauf der For ... Schleife steht das größte Element am Ende des Arrays.
Also muss beim nächsten Durchlauf das vorletzte Element nicht mehr mit dem letzten Element verglichen werden.
Das verringert die Anzahl der zu vergleichenden Elemente bei jedem Durchlauf um 1.

Guter Einwand Sollte dann aber am Anfang vermutlich Last := High(A) - 1 sein, sonst kracht es beim Zugriff auf A[I + 1] .

Nein, beachte das Dec(Last) am Anfang der Repeat Schleife.

[Zacherl]

Zitat von Amateurprofi:

Nein, beachte das Dec(Last) am Anfang der Repeat Schleife.

Stimmt, das hatte ich in der Tat übersehen