AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Treesort

Offene Frage von "Blup"
Ein Thema von johnDelphi · begonnen am 15. Nov 2016 · letzter Beitrag vom 30. Nov 2016
Antwort Antwort
Seite 1 von 2  1 2   
johnDelphi

Registriert seit: 15. Nov 2016
2 Beiträge
 
#1

Treesort

  Alt 15. Nov 2016, 18:23
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.
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#2

AW: Treesort

  Alt 15. Nov 2016, 18:52
Hallo JohnDelphi,

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

Registriert seit: 22. Mär 2003
Ort: Finsterwalde
622 Beiträge
 
Turbo Delphi für Win32
 
#3

AW: Treesort

  Alt 15. Nov 2016, 19:16
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?
Alex Winzer
  Mit Zitat antworten Zitat
Aviator

Registriert seit: 3. Jun 2010
1.583 Beiträge
 
Delphi 10.3 Rio
 
#4

AW: Treesort

  Alt 15. Nov 2016, 19:30
Schau mal beim Sortierkino von Delphi Laie vorbei. Ich meine, dass der SourceCode zur Verfügung steht. Eventuell hat er das Verfahren ja integriert.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.468 Beiträge
 
Delphi 10.1 Berlin Starter
 
#5

AW: Treesort

  Alt 15. Nov 2016, 21:38
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...
Sortierkino und Sortier-Kino
Ob ein Programm wirklich gute Qualität hat, erkennt man am besten dann, wenn man einen unbedarften darauf losläßt.
  Mit Zitat antworten Zitat
freimatz

Registriert seit: 20. Mai 2010
954 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#6

AW: Treesort

  Alt 16. Nov 2016, 11:00
ich brauche den Sortieralgorithmus Treesort
Warum?

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
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.468 Beiträge
 
Delphi 10.1 Berlin Starter
 
#7

AW: Treesort

  Alt 16. Nov 2016, 11:25
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.
Sortierkino und Sortier-Kino
Ob ein Programm wirklich gute Qualität hat, erkennt man am besten dann, wenn man einen unbedarften darauf losläßt.
  Mit Zitat antworten Zitat
Blup

Registriert seit: 7. Aug 2008
1.280 Beiträge
 
Delphi 2007 Professional
 
#8

AW: Treesort

  Alt 16. Nov 2016, 17:24
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.
  Mit Zitat antworten Zitat
johnDelphi

Registriert seit: 15. Nov 2016
2 Beiträge
 
#9

AW: Treesort

  Alt 16. Nov 2016, 17:38
... vielen Dank für die Infos (vor allem an Blup für den Quelltext). Ich denke, damit werde ich klar kommen.
  Mit Zitat antworten Zitat
Delphi-Laie

Registriert seit: 25. Nov 2005
1.468 Beiträge
 
Delphi 10.1 Berlin Starter
 
#10

AW: Treesort

  Alt 16. Nov 2016, 22:27
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.
Sortierkino und Sortier-Kino
Ob ein Programm wirklich gute Qualität hat, erkennt man am besten dann, wenn man einen unbedarften darauf losläßt.

Geändert von Delphi-Laie (16. Nov 2016 um 22:46 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +2. Es ist jetzt 05:15 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf