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)?
Gast
#2473039
Ist der nicht sogar im K&R beschrieben?
Hab mich jetzt schon ein bisschen schlau gemacht und bin auf den BubbleSort-Algorithmus gestoßen. Dieser sollte hoffentlich funktionieren!
Gast
#2473054
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.
Gast
#2473067
DirkB schrieb: >> Ist der nicht sogar im K&R beschrieben? > > Hab ich gerade auf die Schnelle nicht gefunden. Meiner liegt im Auto...
Gast
#2473068
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.
Hier sind verschiedene Sortieralgorithmen recht anschaulich erklärt ;) http://www.youtube.com/watch?v=lyZQPjUT5B4
Danke diese Seite ist wirklich hilfreich!!!
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.
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?
Gast
#2473270
STK500-Besitzer schrieb: > Meiner liegt im Auto... Ich habs im K&R nicht gefunden. Den (1. Auflage, deutsch) hatte ich in der Hand.
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?
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.