Stabiles Sortieren

[gammatester]

Zitat:

Zitat von Namenloser (Beitrag 1372700)

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:

Zitat von Zacherl (Beitrag 1372669)

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:

Zitat von Amateurprofi (Beitrag 1372726)

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 :thumb: Sollte dann aber am Anfang vermutlich

Delphi-Quellcode:

Last := High(A) - 1

sein, sonst kracht es beim Zugriff auf

Delphi-Quellcode:

A[I + 1]

.

[Amateurprofi]

Zitat:

Zitat von Zacherl (Beitrag 1372807)

Zitat:

Zitat von Amateurprofi (Beitrag 1372726)

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 :thumb: Sollte dann aber am Anfang vermutlich

Delphi-Quellcode:

Last := High(A) - 1

sein, sonst kracht es beim Zugriff auf

Delphi-Quellcode:

A[I + 1]

.

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

[Zacherl]

Zitat:

Zitat von Amateurprofi (Beitrag 1372812)

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

Stimmt, das hatte ich in der Tat übersehen :stupid: