Treesort

[johnDelphi]

Hallo Leute,

ich brauche den Sortieralgorithmus Treesort (nicht Binary Treesort!). Im Netz findet sich da sehr wenig. Habe bis jetzt nur bei Wikipedia einen Pseudocode gefunden - und da habe ich Probleme mit der vorletzten Zeile. Die kann ich nicht so richtig deuten.

für i := ⌊i÷2⌋ solange i > 0 ???

Also - wenn mir jemand einen Quelltext oder irgendeinen sinnvollen Link senden könnte, wäre ich sehr dankbar.

[Namenloser]

Hallo JohnDelphi,

⌊i÷2⌋ bedeuted "i÷2, abgerundet", also in Delphi i div 2 . Siehe Gaußklammer.

[Schwedenbitter]

Die Lösung würde mich am Ende auch mal interessieren.
Ich habe sowohl im Pseudocode als auch in der Wortbeschreibung das ∞ gelesen. Löst man das dann über ein zweidimensionales Array mit Pointern und setzt das dann nil?

[Aviator]

Schau mal beim Sortierkino von Delphi Laie vorbei. Ich meine, dass der SourceCode zur Verfügung steht. Eventuell hat er das Verfahren ja integriert.

[Delphi-Laie]

Zitat von Aviator:

Schau mal beim Sortierkino von Delphi Laie vorbei. Ich meine, dass der SourceCode zur Verfügung steht. Eventuell hat er das Verfahren ja integriert.

Nicht daß ich wüßte, leider nicht.

Ich habe einige binärbaumbasierte Sortieralgorithmen implementiert, dabei aber immer von der Leistung anderer "schmarotzt".

Natürlich wurde ich sofort hellhörig (eher "hellsichtig" ohne prophetische Gabe sozusagen), als ich einen mir unbekannten Sortieralgorithmus las.

Ich werde mal versuchen, ihn anhand der Wikipedia-Beschreibung, die recht fundiert erscheint, zu implementieren. Mit dynamischen Datenstrukturen scheint er ja nichts zu tun zu haben, zum Glück, denn darin würde ich mich wohl hoffnungslos verfangen. Derlei Datenstrukturen sind wohl auch für Informatiker gehoben und eine echte Programmierherausforderung. Wenn ich daran denke, was für eine Qual das mit meinen ersten beiden war...

[freimatz]

Zitat von johnDelphi:

ich brauche den Sortieralgorithmus Treesort

Warum?

Zitat von Delphi-Laie:

Natürlich wurde ich sofort hellhörig (eher "hellsichtig" ohne prophetische Gabe sozusagen), als ich einen mir unbekannten Sortieralgorithmus las.

https://de.wikipedia.org/wiki/Katego...ieralgorithmus

[Delphi-Laie]

Zitat von freimatz:

Zitat von Delphi-Laie:

Natürlich wurde ich sofort hellhörig (eher "hellsichtig" ohne prophetische Gabe sozusagen), als ich einen mir unbekannten Sortieralgorithmus las.

https://de.wikipedia.org/wiki/Katego...ieralgorithmus

Danke, natürlich kenne ich diese Übersicht, bin aber noch nicht auf Treesort aufmerksam geworden. Vermutlich las ich es vor Jahren schon mal, doch evtl. hat mich der "Vorläufer von Heapsort" abgeschreckt, ich weiß es nicht mehr.

Sonderlich gut werde ich ihn ohnehin nicht visualsiert / animiert bekommen, weil "Zwischenstrukturen" (die Zuhilfenahme zusätzlichen Speichers) mit diesem simplen Darstellungskonzept nicht abbildbar sind.

[Blup]

Delphi-Quellcode:

unit Treesort;

interface

uses
  Types;

function Sort(const AItems: TIntegerDynArray): TIntegerDynArray;

implementation

type
  TTreeItem = record
    Value: Integer;
    Index: Integer;
    class function New(const AValue, AIndex: Integer): TTreeItem; static;
    class function Min(const a, b: TTreeItem): TTreeItem; static;
    procedure Clear;
    function IsNull: Boolean;
  end;

class function TTreeItem.New(const AValue, AIndex: Integer): TTreeItem;
begin
  Result.Value := AValue;
  Result.Index := AIndex;
end;

class function TTreeItem.Min(const a, b: TTreeItem): TTreeItem;
begin
  if b.IsNull then
    Result := a
  else if a.IsNull then
    Result := b
  else if a.Value <= b.Value then
    Result := a
  else
    Result := b;
end;

procedure TTreeItem.Clear;
begin
  Value := 0;
  Index := 0;
end;

function TTreeItem.IsNull: Boolean;
begin
  Result := (Value = 0) and (Index = 0);
end;

function CalcDiv2(var AValue: Integer): Boolean;
begin
  AValue := (AValue div 2);
  Result := (AValue > 0);
end;

function Sort(const AItems: TIntegerDynArray): TIntegerDynArray;
var
  m: array of TTreeItem;
  n, i, j: Integer;
begin
  n := Length(AItems);
  SetLength(m, n * 2);
  {erste Hälfte initialisieren - eigentlich nicht notwendig}
  for i := 0 to n - 1 do
    m[i].Clear;
  {zweite Hälfte des Arrays verweist auf die unsortierten Elemente}
  for i := 0 to n - 1 do
    m[n + i] := TTreeItem.New(AItems[i], n + i);
  {erste Hälfte des Array durch Vergleich}
  for i := n - 1 downto 1 do
    m[i] := TTreeItem.Min(m[2 * i], m[2 * i + 1]);

  SetLength(Result, n);
  for j := 0 to n - 1 do
  begin
    Result[j] := m[1].Value;
    i := m[1].Index;
    m[i].Clear;
    while CalcDiv2(i) do
      m[i] := TTreeItem.Min(m[2 * i], m[2 * i + 1]);
  end;
end;

end.

[johnDelphi]

... vielen Dank für die Infos (vor allem an Blup für den Quelltext). Ich denke, damit werde ich klar kommen.

[Delphi-Laie]

Auch von mir ein herzliches Dankeschön, Blub!

Darf ich fragen, ob Du diesen Quelltext schon in petto hattest oder erst jüngst aufgrund dieser Diskussion erstelltest?

Meine Befürchtung ist weiterhin, daß dieses Sortieralgorithmus' Animation kein sonderlicher optischer Leckerbissen sein dürfte, aber das ist für mich schon lang kein Auschlußkriterium mehr, etwas zu implementieren.