Stabiles Sortieren

[Der schöne Günther]

Meistens reicht mir das Sortieren über TArray.Sort<T>(..) da man auch einen eigenen Comparer angeben kann. Laut Doku ist die Implementierung ein QuickSort, also nicht stabil - Es ist also nicht garantiert dass Elemente mit gleicher Wertigkeit nach dem Sortieren auch noch in der gleichen Reihenfolge zueinander stehen.

Gibt es in der RTL ein stabiles Sortierverfahren oder muss man das selbst machen?

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

[Uwe Raabe]

Du kannst auch statt T einen Record aus T und dem Index sortieren. Der Comparer muss dann natürlich bei gleichem T den Index vergleichen.

[Der schöne Günther]

Danke für den Bubble Sort. Der ist mir vielleicht sogar lieber, denn Geschwindigkeit ist mir grade nicht wichtig, Speicher aber schon eher.

Ich habe einfach mal den Pseudo-Code auf Wikipedia abgetippt, noch keine vernünftigen Tests, aber im Debugger scheinen die Dinge richtig sortiert zu sein.

Delphi-Quellcode:

uses
  System.SysUtils,
  System.Generics.Collections,
  System.Generics.Defaults;

type
   _TArray = class(System.Generics.TArray)
      private
         /// <param name="input">
            ///     Muss mindestens zwei Elemente enthalten
         /// </param>
         class procedure SplitValues<T>(
            const   input:   TArray<T>;
            out      left:   TArray<T>;
            out      right:   TArray<T>
         );
         class function MergeValues<T>(const left, right: TArray<T>; const Comparer:
            IComparer<T>): TArray<T>;
      public
         class procedure MergeSort<T>(var Values: TArray<T>; const Comparer:
            IComparer<T>); static;
   end;

{ _TArray }

class procedure _TArray.MergeSort<T>(var Values: TArray<T>; const Comparer:
   IComparer<T>);
var
   leftValues, rightValues: TArray<T>;
begin
    // Quelle :https://de.wikipedia.org/w/index.php?title=Mergesort&oldid=164969688#Implementierung
   if Length(Values) <= 1 then Exit;

   splitValues<T>(Values, leftValues, rightValues);
   _TArray.MergeSort<T>(leftValues, Comparer);
   _TArray.MergeSort<T>(rightValues, Comparer);

   Values := MergeValues<T>(leftValues, rightValues, Comparer);
end;

class function _TArray.MergeValues<T>(
   const left, right: TArray<T>;
   const Comparer: IComparer<T>
): TArray<T>;
var
   leftList:   TList<T>;
   rightList:   TList<T>;
   resultList:   TList<T>;

begin
    // Quelle: https://de.wikipedia.org/w/index.php?title=Mergesort&oldid=164969688#Implementierung
   resultList := TList<T>.Create();

   leftList := TList<T>.Create(); leftList.AddRange(left);
   rightList := TList<T>.Create(); rightList.AddRange(right);

   // "solange (linkeListe und rechteListe nicht leer)"
   while( (leftList.Count > 0) and (rightList.Count > 0) ) do begin
      // "falls (erstes Element der linkeListe <= erstes Element der rechteListe)"
      if (Comparer.Compare(leftList.First(), rightList.First()) <= 0) then
         // "dann füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe"
         begin
            resultList.Add(   leftList.First() );
            leftList.Delete(0);
         end
      else
         // "sonst füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe"
         begin
            resultList.Add( rightList.First() );
            rightList.Delete(0);
         end
      ;
   end;

   // "solange (linkeListe nicht leer)"
   while(leftList.Count > 0) do begin
      // "füge erstes Element linkeListe in die neueListe hinten ein und entferne es aus linkeListe"
      resultList.Add( leftList.First() );
      leftList.Delete(0);
   end;

   // "solange (rechteListe nicht leer)"
   while(rightList.Count > 0) do begin
      // "füge erstes Element rechteListe in die neueListe hinten ein und entferne es aus rechteListe"
      resultList.Add( rightList.First() );
      rightList.Delete(0);
    end;

   Result := resultList.ToArray();
end;

class procedure _TArray.SplitValues<T>(
   const input: TArray<T>;
   out left, right: TArray<T>
);
var
   inputLength:    Integer;
   leftLength:      Integer;
begin
   inputLength := Length(input);
   leftLength := inputLength div 2;

   SetLength(left, leftLength);
   SetLength(right, inputLength - leftLength);

   TArray.Copy<T>(input, left, Low(input), 0, leftLength);
   TArray.Copy<T>(input, right, Low(input)+leftLength, 0, inputLength - leftLength);
end;

Ich glaube ich nehme trotzdem deinen BubbleSort 8-)


Das mit dem Wrapper-Record und Comparer der zusätzlich noch über den Index vergleicht ist (typisch Uwe) ziemlich tricky, da wäre ich nie drauf gekommen.


PS: Und ja, in jedem MergeValues neue TList-Instanzen erstellen (Bonus: Und niemals freigeben) ist vielleicht auch nicht so dolle. Ich will aber langsam Feierabend haben...

[Zacherl]

Zitat:

Zitat von Uwe Raabe (Beitrag 1372670)

Du kannst auch statt T einen Record aus T und dem Index sortieren. Der Comparer muss dann natürlich bei gleichem T den Index vergleichen.

Kannst du das evtl. anhand von etwas Code nochmal erläutern? Das klingt interessant, aber ich bin grade nicht sicher, ob du das gleiche meinst, was ich mir darunter vorstelle :stupid:

[p80286]

es soll allerdings auch schnellere Sortierverfahren, die stabil sind z.b. BinaryTree...

Gruß
K-H

[Namenloser]

Zitat:

Zitat von p80286 (Beitrag 1372685)

es soll allerdings auch schnellere Sortierverfahren, die stabil sind z.b. BinaryTree...

Die einfachste Variante ist immer noch, einfach einen aufsteigenden Index an das Sortierkriterium anzuhängen, sodass die Sortierung immer eindeutig ist. So bekommt man jedes Sortierverfahren stabil, selbst Quicksort.

Oder wenn du Objekte sortierst (also Pointer), dann kannst du auch einfach gleich die Pointer vergleichen.

Also in der Art:

Delphi-Quellcode:

TRecord = record
  Name: String;
  Id: Integer;
end;

function Compare(const a, b: TRecord): integer;
begin
  Result := StrCompare(a.Name, b.Name);
  if (Result = 0) then
    Result := b.Id - a.Id;
end;

[p80286]

Zitat:

Zitat von Namenloser (Beitrag 1372686)

dann kannst du auch einfach gleich die Pointer vergleichen.

Ausgerechnet das funktioniert nicht, da Du Dich nicht darauf verlassen kannst, daß Pointer(Speicheradressen) nicht zufällig sind. Du brauchst immer eine Relation zwischen den Daten(sätzen) sei es .next/.last oder der Index eines Arrays.

Gruß
K-H

[Delphi-Laie]

Zitat:

Zitat von p80286 (Beitrag 1372685)

es soll allerdings auch schnellere Sortierverfahren, die stabil sind z.b. BinaryTree...

Binarytreesort benötigt nach meinem Wissen erheblich zusätzlichen Speicher und ist zudem kompliziert. Das Gefummel mit den dynamischen Datenstrukturen ist sogar bei Informatikern fehleranfällig und zurecht die "Königsdisziplin".

Wenn es denn ein einfacher ("elementarer") Sortieralgorithmus sein soll, dann rate ich statt zu Bubblesort dann eher zu Insertionsort, das ist ein Quentchen schneller.

Wenn man es komplizierter akzeptiert und / oder zusätzlicher Speicher keine Rolle spielt (i.d.R. benötigt man aber dann maximal den Speicher, den die zu sortierende Elementemenge benötigt, noch einmal zusätzlich), dann stehen einem eine schier unglaubliche Fülle an Sortierverfahren zur Verfügung, auch stabile, die zudem fast alle schneller als Bubble- bzw. Insertionsort sind.

[Namenloser]

Zitat:

Zitat von p80286 (Beitrag 1372694)

Ausgerechnet das funktioniert nicht, da Du Dich nicht darauf verlassen kannst, daß Pointer(Speicheradressen) nicht zufällig sind. Du brauchst immer eine Relation zwischen den Daten(sätzen) sei es .next/.last oder der Index eines Arrays.

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.

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