Einfache Alternative zu TList.Sort?

Gausi · Verfasst: Mo 17.01.05 10:50

Ich benutze die Methode Sort, um ein paar TObjectlisten zu sortieren.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

function Sortieren_Pfad(item1,item2:pointer):integer;
begin
  result:=comparestr(AnsiUppercase(TObject1(item1).String1), AnsiUppercase(TObject1(item2).string1))
end;
[...]
  // Aufruf mit
  Liste1.Sort(Sortieren_Pfad);

Sortierverfahren ist laut OH Quicksort, was ja bekannterweise in aller Regel sehr schnell ist.

Ich kann aber sehr leicht Fälle konstruieren (und die können in meiner Anwendung durchaus "zufällig" entstehen), in der Quicksort ungefähr genauso "schnell" ist wie Bubblesort.
Es scheint so zu sein, dass bei Listen der Form 1,2,3,4,...10000,1,2,3,4,...,10000 der Quicksort versagt. Evtl. kann das ja auch einer mal verifizieren.

Kann man irgendwie weiter in die Methode Sort eingreifen (um z.B. bei der Wahl des Pivotelements nicht immer die Mitte der Folge zu nehmen) oder bleibt mir nichts anderes übrig, als mein eigenes Sortierverfahren zu schreiben?

Moderiert von UGrohne: Topic aus Sonstiges verschoben am Mo 17.01.2005 um 13:44

_________________
We are, we were and will not be.

IngoD7 · Beiträge: 629 D7

Gausi hat folgendes geschrieben:

Es scheint so zu sein, dass bei Listen der Form 1,2,3,4,...10000,1,2,3,4,...,10000 der Quicksort versagt. Evtl. kann das ja auch einer mal verifizieren.

Das braucht niemand tun, das ist so.

Mit so einer Liste erreichst du, dass, wenn als Pivotelement das mittlerste der Liste gewählt wird, der worst case eintritt. Das mittlerste wird in der Regel genommen, wie du schon geschrieben hast. Die Sort-Methode tut das auch. Es wird also genau das größte (10000) oder genau das kleinste Element (1) als Pivotelement genommen, was bei Quicksort das schlechteste Verhalten (worst case) auslöst.

Gausi hat folgendes geschrieben:

Kann man irgendwie weiter in die Methode Sort eingreifen (um z.B. bei der Wahl des Pivotelements nicht immer die Mitte der Folge zu nehmen)

Klar. Leite eine Klasse von TObjectList ab und überschreibe die Methode Sort, welche von TList abgeleitet ist. Ich habe aber keine Ahnung, ob und wie das geht.

Gausi hat folgendes geschrieben:

oder bleibt mir nichts anderes übrig, als mein eigenes Sortierverfahren zu schreiben?

Nicht unbedingt. Wenn du weißt, dass deine Liste so aussieht, wie oben beschrieben (vielleicht kann dein Programm das ja abprüfen), dann kannst du vor dem Sortieren ein Element von der ersten Viertelgrenze der Liste (das hätte dann so einen Wert von ca. 5000) in die Mitte der Liste setzen (verschieben, tauschen) und danach die Methode Sort aufrufen. Sollte Wunder wirken.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme