TListView automatisch Sortieren

[robinWie]

Hallo,
ich habe ein TListVie mit 2 Spalten. In der ersten stehen Zahlen, in der zweiten sind Namen. Das ganze soll Charts darstellen. Die Zahlen in der 1. Spalte geben an, wie of ein Lied gespielt wurde. Ich will jetzt, dass die Liste immer wenn was hinzugefügt wird, alles Sortiert wird. Und zwar so, dass oben die Titel stehen, die am meisten gespielt wurden, und unten die am wenigesten gespielt wurden. Ich habe schon viel gebastelt, aber bekomme es einfach nicht gebacken.

Weiss jemand einen Algorithmus oder sowas, der das kann?

Danke im Voraus
Robin

[Der_Unwissende]

Zitat von robinWie:

Weiss jemand einen Algorithmus oder sowas, der das kann?

Äh, fragst Du gerade nach einem Sortier-Algorithmus? Also da solltest Du auch mindestens einen kennen, aber können tun das im u.A.: Bubblesort, Shellsort, InsertionSort, Quicksort, MergeSort, HeapSort, .... (mal nur ein paar die mir gerade einfallen). An sich kann das also jeder dieser Algorithmen, die Geschwindigkeit dürfte sich aber teilweise deutlich unterscheiden. Am Besten sind hier (mal etwas OT) übrigens auch eher Mischungen aus mehr als einem Algorithmus (da der Bubblesort z.B. für sehr kleine Mengen schneller arbeitet als Quicksort, bei großen sieht das aber ganz anders aus). Hier wird man also mit Quicksort beginnen (der teilt die Gesamtmenge in Teilmengen auf) und irgendwann (wenn die Teilmengen klein genug sind) die einzelnen Teilmengen mit einem anderen Algorithmus sortieren.

Aber für dein Problem geht das ganze auch ein wenig einfacher. Keiner der hier genannten Sortieralgorithmen ist auf einen bestimmten Datentypen beschränkt. Schaust Du Dir deren Algorithmus an, so wirst Du hier häufig etwas abstrakt einen Vergleich zwischen zwei Elementen finden. Welchen Typ diese Elemente haben ist egal, Du musst nur bestimmen können welches größer/kleiner ist (oder ob beide gleich sind).
TListView bietet Dir mit der Methode CustomSort einen fertigen Sortieralgorithmus an. Jetzt weiß dieser Algorithmus aber nicht, wie Du sortieren möchtest (Aufsteigend oder absteigend? Sind die Werte als Zahlen zu interpretieren?...). Deshalb musst Du der Methode CustomSort eine Vergleichsfunktion mitgeben, die für zwei Elemente zurückgibt, wie sie sich zueinander verhalten.
Dazu übergibst Du der Funktion eine Funktion vom Typ TLvCompare. Die Argumente der Funktion (und den Rückgabewert) kannst Du der OH entnehmen.

So bekommst Du zwar sehr leicht eine sortierte Liste, es gibt aber noch einen anderen (vielleicht sinnvolleren) Weg für dein Problem. Sortieren bietet sich immer für eine ungeordnete Menge an. Die schlechteste Laufzeit hat der Quicksort-Algorithmus zum Beispiel immer dann, wenn die zu sortierende Menge bereits sortiert ist (tatsächlich muss hier aber auch das Pivot-Element noch ungünstig gewählt werden). Aber an sich ist das Sortieren einer sortierten Menge einfach mit einem unnötigen Zeitaufwand verbunden (sollte klar sein).
Hast Du also eine sortierte Menge und möchtest nun ein weiteres Element hinzufügen, so musst Du nichts weiter tun, als dieses Element an die korrekte Position in diese sortierte Menge einzufügen. Natürlich kann es sein, dass Du das Element zwischen zwei andere einfügen musst, das kannst Du aber sehr leicht tun, da die Sortierung für alle folgenden und vorhergehenden Elemente aufrecht erhalten bleibt. Das einfügen kannst Du also in konstanter Zeit vornehmen. Hier nimmt Dir die Methode Insert der Eigenschaft Items der TListView die ganze Arbeit ab. Du gibst nur die Position an, an die eingefügt werden soll, den Rest macht die Methode für Dich.
Bleibt also noch die Frage, an welcher Stelle Du einfügen möchtest. Aber auch hier lässt sich ausnutzen, dass Du ja bereits eine sortierte Menge hast. Der einfachste Weg ist einfach von oben bis unten die Items durchzugehen und an der richtigen Stelle zu stoppen. Geht aber noch ein wenig effizienter, indem Du einfach die Position einschränkst. Als erstes kannst Du schauen, ob das neue Element vor das Erste oder hinter das Letzte Element gehört. Ist dies Nicht der Fall, so kannst Du einfach die Mitte der sortierten Menge betrachten. Je nachdem ob das neue Element hier einen kleineren oder größeren Wert hat, brauchst Du nur noch die Hälfte des Feldes betrachten. So kannst Du rekursiv weiter machen und benötigst für das Einfügen eines neuen Elements nur max. O(log(n)) Zeit, und das ist schneller als jedes Sortieren!

Gruß Der Unwissende

[marabu]

Hallo,

ich würde sogar noch einen Schritt weiter gehen und behaupten, dass bei einer (absteigend )vorsortierten Liste überhaupt keine Neusortierung nötig ist. Für das zuletzt abgespielte Lied muss einfach nur geprüft werden, ob es nach dem Inkrementieren seines Zählers mit seinem Vorgänger den Platz tauschen muss oder nicht.

Freundliche Grüße vom marabu