Stabiles Sortieren

[gammatester]

Zitat von Namenloser:

Sie sind zufällig, aber sie ändern sich aber nicht plötzlich zwischen zwei Sortierdurchläufen. Hier müsste man vielleicht genauer definieren, was man unter "stabil" versteht.

Allerdings müßten sie zu Anfang strikt monoton sein (kein Problem bei Arrays, aber da kan mann gleich die Indices nehmen).

[Namenloser]

Ja ok, du hast streng genommen recht. Allerdings habe ich stabile Sortierverfahren bisher eigentlich immer nur gebraucht, wenn ich nicht wollte, dass die Einträge bei wiederholtem Sortieren zufällig hin- und herspringen. Ich hatte jetzt von der Ecke aus gedacht.

[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