Sortieren der Einträge in einer einfach verketteten Liste

[Hans M. (fuxdancer)]

Hallo!
Könnte mir jemand einen einfach Algorithmus (wenn möglich in der 
Programmiersprache C) zeigen, mit welchem man in einer einfach 
verketteten Liste die Listeneinträge nach einer ID sortieren kann 
(Unsigned Integer)?

[STK500-Besitzer (Gast)]

Ist der nicht sogar im K&R beschrieben?

[Hans M. (fuxdancer)]

Hab mich jetzt schon ein bisschen schlau gemacht und bin auf den 
BubbleSort-Algorithmus gestoßen. Dieser sollte hoffentlich 
funktionieren!

[DirkB (Gast)]

Du fängst beim ersten Eintrag an
- und vergleichst ihn mit dem darauffolgenden.
- Evtl. vertauschen (Zeiger verbiegen)
- Dann gehst du einen Eintrag weiter und vergleichst ... (siehe zweite 
Zeile)
Das machst du solange, wie Elemente vertauscht wurden.


STK500-Besitzer schrieb:
> Ist der nicht sogar im K&R beschrieben?

Hab ich gerade auf die Schnelle nicht gefunden.

[STK500-Besitzer (Gast)]

DirkB schrieb:
>> Ist der nicht sogar im K&R beschrieben?
>
> Hab ich gerade auf die Schnelle nicht gefunden.

Meiner liegt im Auto...

[STK500-Besitzer (Gast)]

Hans M. schrieb:
> Hallo!
> Könnte mir jemand einen einfach Algorithmus (wenn möglich in der
> Programmiersprache C) zeigen, mit welchem man in einer einfach
> verketteten Liste die Listeneinträge nach einer ID sortieren kann
> (Unsigned Integer)?

Übrigens sollte man so eine Liste schon beim erstellen sortieren.

[Hans-Georg L. (h-g-l)]

Hier sind verschiedene Sortieralgorithmen recht anschaulich erklärt ;)

http://www.youtube.com/watch?v=lyZQPjUT5B4

[Hans M. (fuxdancer)]

Danke diese Seite ist wirklich hilfreich!!!

[Daniel F. (df311)]

ich würde den schon erwähnten bubblesort oder evtl. einen modifizierten 
selectsort (bereits sortierte elemente aus der ursprünglichen liste 
entfernen und an eine neue anhängen) verwenden...

wegen der linked-list-struktur sollte der zusätzliche speicherbedarf 
minimal sein.

[Klaus W. (mfgkw)]

Eine ganz andere Frage ist, ob eine Liste die beste Struktur ist, wenn 
Daten sortiert werden müssen.

Wer sagt, daß es eine Liste sein muß, und warum?

[DirkB (Gast)]

STK500-Besitzer schrieb:
> Meiner liegt im Auto...

Ich habs im K&R nicht gefunden. Den (1. Auflage, deutsch) hatte ich in 
der Hand.

[Arc N. (arc)]

Klaus Wachtler schrieb:
> Eine ganz andere Frage ist, ob eine Liste die beste Struktur ist, wenn
> Daten sortiert werden müssen.

Merge Sort funktioniert damit (einfach verketteten Listen) wunderbar in 
O(n log n)...

> Wer sagt, daß es eine Liste sein muß, und warum?