Insertion Sort Problem

[r2c2]

Zitat von Der_Unwissende:

Zitat von r2c2:

Für was out-of-place sortieren?

Um die einfache Idee zu vermitteln.

Also ich würde sagen out-of-place is bei verketteten Listen eher komplizierter, da man jeweils die einzelnen Items neu erzeugen muss(siehe unten).

Zitat:

Das heißt, das die zweite Liste auch einfach ein zweiter Zeiger sein kann, wobei dann ein Zeiger auf das letzte Element der sortierten Liste und der andere auf das erste Element der unsortierten Liste zeigt. Dabei zeigen beide Zeiger eigentlich auf die selbe Strucktur, nur auf unterschiedliche Elemente.

Das wäre aber auch wieder in-plcae, da du die Daten nicht doppelt im Speicher hast. Du hast eben nur n 2. Pointer. Und den brauchst du sowieso, weil du den Anfang des unsortieren Bereiches braucht. Welche Pointer baucht man nun fürs In-place-sortieren einer einfach veketteten Liste mit InsertionSort mindestens?
- Root-Pointer(der is eigentlich sowieso da)
- Pointer auf das gerade betrachtete Element
- Pointer, der auf den Anfang des unsortierten Bereiches(bzw. auf das nächste zu sortierende Element) zeigt[1]
- Pointer, der den sortierten Bereich durchläuft.

Zitat:

Nur wie gesagt, erstmal ist es vielleicht leichter, nur den Insertion-Sort mit zwei Listen zu verstehen, da ist schon das Einfügen in der sortierten Liste und das Löschen aus der unsortierten drin.

Ob man sich jetzt den Pointer auf den unsortierten Bereich als zweite Liste vorstellt oder als pointer in die Liste is mwhr oder weniger egal. Trotzdem isses in-place...

[1] Könnte man zwar weglassen, aber dann hat man wider zig vergleiche mehr zu machen...

mfg

Christian