Splaytree-Animation

[Furtbichler]

Zitat von Delphi-Laie:

Frag mich was leichteres

Wie gehts?

Zitat:

ich bin kein Informatiker.

Nur das Ergebnis zählt (ja, der Weg auch).

Das ist ein Binärbaum, der 'einfach' das zuletzt gesuchte Element als neue Wurzel bzw. Top-Element speichert und dadurch den Baum umformt. Das führt dazu, das oft benötigte Elemente tendentiell weiter oben liegen, was zu einer 'Suchoptimierung' führt.

Als Sortieralgorithmus dürfte sich das imho nicht lohnen, denn beim Sortieren wird zwar oft verglichen, aber selten direkt gesucht. Aber ich lasse mich gerne eines Besseren belehren.

[Delphi-Laie]

Zitat von Furtbichler:

Zitat von Delphi-Laie:

Frag mich was leichteres

Wie gehts?

Blendend, nachdem ich bei der "Extraktion" des eigentlichen Algorithmus und Quellcodevereinfachung weit vorangeschritten bin.

Zitat von Furtbichler:

Als Sortieralgorithmus dürfte sich das imho nicht lohnen, denn beim Sortieren wird zwar oft verglichen, aber selten direkt gesucht. Aber ich lasse mich gerne eines Besseren belehren.

Lohnen? Für mein Sortieranimationsprogramm lohnt sich jeder Algorithmus. Und wenn die Arbeitsweise dabei nicht offensichtlich wird, dann erlaubt das zumindest doch eine erste Abschätzung der Geschwindigkeit (wenn auch keine sichere "gefühlte" Zuordnung zur Komplexitätsklasse, s. z.B. Select(ion)sort (das läuft bei mir schnell, ist aber dennoch O(n^2)).

Splaysort benötigt, wie die anderen, auf dynamischen Speicherstrukturen beruhenden Algorithmen (in die eingeordnet und aus denen gelesen wird), reichlich zusätzlichen Speicher, ist also ex situ, allerdings von der Geschwindigkeit her O(n*log(n)). Erste "ungraphische" Ergebnisse scheinen das zu bestätigen.