Verkettete Liste schnell sortieren

[thekiller]

Moin moin,

brauch mal wieder bisschen Rat^^

Der Aufbau der Liste ist folgender:
- Eine Klasse die alle Elemente der Liste verwaltet
- Jedes Element ist eine Instanz einer Klasse und zeigt auf das vorige und nächste Element in der Liste

Also eine ganz einfache Liste...
Die Manager-Klasse soll nun mit einer Methode erweitert werden welche alle Elemente der Liste schnellstmöglich nach Größe sortiert.

Ich hatte überlegt in der Methode eine weitere Liste derselben Art anzulegen, dann im Sortiervorgang z.B. das Element mit dem größten Wert in die neue Liste einreihen und aus der originalen Liste herausnehmen, damit Sie beim nächst größten Element nicht mehr auftaucht.
Wenn der Sortiervorgang komplett durchgelaufen ist, sind alle Elemente sortiert in der neuen Liste. Nun könnte ich die Elemente ja nacheinander wieder an die originale Liste anhängen bzw. den Pointer des ersten Elements der Managerklasse übergeben.
So zumindest meine Überlegung.

Gibts da vielleicht ne bessere/schnellere Möglichkeit?

MfG Manuel

 

[deepthroat]

Hi.

Warum willst du nicht std::list verwenden?

Oder du verwendest boost::intrusive::list.

Ansonsten, Sortieralgorithmen sind doch nicht wirklich etwas, was man sich selbst überlegt. Nimm InsertionSort oder SelectionSort. Und eine temporäre Liste ist auch nicht sinnvoll, das kannst du genauso gut in situ machen.

Gruß

 

[thekiller]

std::list gibt mir nicht die Möglichkeiten die ich benötige. Ich muss da sehr flexibel bleiben.

Eine andere Art der Liste wie z.B. die die du vorgeschlagen hast kommen nicht in Frage.

Ja diese Algorithmen sind mir bekannt aber welche davon ist die schnellste Möglichkeit in Bezug auf verkettete Listen? Ist ja schließlich etwas anderes als ein Array zu sortieren, da muss man ja nur die Werte vertauschen. Bei einer Liste aber auch die Verweise aufs vorige/nächste Element.

 

[deepthroat]

std::list gibt mir nicht die Möglichkeiten die ich benötige. Ich muss da sehr flexibel bleiben.

Inwiefern?

Eine andere Art der Liste wie z.B. die die du vorgeschlagen hast kommen nicht in Frage.

Warum?

Ja diese Algorithmen sind mir bekannt aber welche davon ist die schnellste Möglichkeit in Bezug auf verkettete Listen? Ist ja schließlich etwas anderes als ein Array zu sortieren, da muss man ja nur die Werte vertauschen. Bei einer Liste aber auch die Verweise aufs vorige/nächste Element.

Beide Algorithmen haben ungefähr den gleichen Aufwand.

Über wieviel Elemente redest du denn? Kannst du die Liste nicht generell sortiert vorhalten?

Gruß

 

[thekiller]

Zitat von thekiller
std::list gibt mir nicht die Möglichkeiten die ich benötige. Ich muss da sehr flexibel bleiben.
Inwiefern?

Einige meiner verketteten Listen beziehen sich aufeinander und dafür gibt es bestimmte Methoden in meinen Managerklassen.

Zitat von thekiller
Eine andere Art der Liste wie z.B. die die du vorgeschlagen hast kommen nicht in Frage.
Warum?

Der Aufwand mein Projekt nach std::list oder anderen umzuprogrammieren wäre enorm...

Zitat von thekiller
Ja diese Algorithmen sind mir bekannt aber welche davon ist die schnellste Möglichkeit in Bezug auf verkettete Listen? Ist ja schließlich etwas anderes als ein Array zu sortieren, da muss man ja nur die Werte vertauschen. Bei einer Liste aber auch die Verweise aufs vorige/nächste Element.
Beide Algorithmen haben ungefähr den gleichen Aufwand.

Ok. Ich habe mich für Selection-Sort entschieden. Das erscheint mir am besten.

Über wieviel Elemente redest du denn?

Keine Ahnung, deswegen ja die Liste...

Kannst du die Liste nicht generell sortiert vorhalten?

Nein, da die Anzahl der Elemente sich sehr schnell verändern kann und die Werte nach denen ich sortiere auch verändert werden.