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


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

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

[p80286]

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

Gruß
K-H

[Namenloser]

Zitat von p80286:

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 von Namenloser:

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 von p80286:

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 von p80286:

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.