einfach verkettete Liste und Insertion Sort

[xus]

hi!

Ich hätte mal eine Verständnisfrage zu einfach verketteten Listen:

Gegeben sei eine einfach verkettete Liste. gefüllt mit integer zahlen.

können diese Zahlen mit insertion Sort sortiert werden?

Ich glaube nicht, da ja in einer einfachverkettete Liste nur elemente in eine Richtung verglichen werden können, oder?

Quick, bzw. Heapsort würde dem nach auch nicht funktioniern, da die Elemente die verglichen werden müssten ja gar nicht direkt zusammenhängen oder?

irr ich mich da komplett oder stimmen meine Volgerungen?

lg, XuS

ps: Wie schauts mit Merge Sort aus?

 

[SlaterB]

grundsätzlich kann man mit einer einfach-verketteten Liste ALLES machen, notfalls nur mit etwas mehr Aufwand,
z.B. ein Elemente zwei Positionen weiter vorne einfügen: Liste von Anfang an durchlaufen, die passende Position finden, dort einfügen,

bei Sortieralgorithmen ist die Frage generell etwas deplaziert, da diese gar nicht mal die Originalliste groß benutzen müssen,
sondern sich alles in Teillisten/ Arrays kopieren können/ müssen/ dürfen/ wollen/ sollen blah blah

grundsätzlich gilt aber hier wie oben: wenn man nur genug Aufwand reinsteckt, kann man die Algorithmen wie alle anderen auch
mit vielen 'einfach verkettete Listen' oder gar nur der einen Originaliste umsetzen

 

[xus]

danke für die antwort. ich weis das es schwachsinnig ist, aber ich muss es trozdem lösen da es eine aufgabe für mein studium ist. das problem ich bin im SS eingestiegen und weis jetzt nicht so viel über verkettete listen.

Die genaue Aufgabenstellung war:

Es sei eine einfach verkettete Liste gegeben. Welche Probleme ergeben sich bei Einsatz folgender Sortierverfahren:
a) Insertion Sort
b) Quicksort
c) Heapsort
d) Mergesort
Wie verändern sich die Laufzeiten der Algorithmen? Überlegen sie sich geeignete Datenstrukturen (andere
als Arrays), um Verbesserungen zu erzielen.

Das bedeutet ich kann jetzt alle Sortieralgorithmen auch in einfach verketteten listen durchführen. Dann müsste ich halt bei Insertion Sort statt rückwerts mit dem Element vorwärts laufen. aber was ich nicht versthe ist folgendes:

Verkettete Liste mit Elementen: 3 5 8 6 9.

bis 3,5,8 ist alles perfekt sortiert nun komm ich zum 6er. aber wie kann ich den 6er mit dem 3 vergleichen? rückwerts kann ich nicht da die liste nur einfach verkettet ist also vom 6er komm ich nur zum 9er. komm ich vom 9er wieder zum 3?

lg, XuS

 

[SlaterB]

von vorwärts zu laufen wäre wohl ein ganz anderer Algorithmus, inwiefern das erlaubt ist, kann ich nicht interpretieren,
in dem Fall müsstest du erstmal die 6 ganz rauslöschen,
dann beginnst du von vorne, wieso sollte sich die 6 nicht mit der 3 vergleichen lassen? 6 in einer Variablen, 3 das aktuelle Listenelement,
Vergleich und gut ist,
man könnte sich nun sparen, die 6 ganz vorne einzufügen und dann immer zu tauschen, wie man es von hinten machen würde
(wenn ich mich nach
http://de.wikipedia.org/wiki/Insertionsort
richte)
sondern von vorne die Position suchen und dann EINMAL einfügen,

--------

auch der Durchlauf von hinten ginge, die 6 also mit der 8 vergleichen und gegebenfalls tauschen,
wie die 8 finden? na die Liste nochmal durchlaufen, wenn der Nachfolger eines Elementes x die 6 ist, dann x selber der Vorgänger

so, schon viel zu viel erzählt, das sollst du eigentlich selber machen