Stabiles Sortieren

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