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