Insertion Sort Problem

[dragi]

Hallo zusammen,

ich habe eine verkettete Liste die ich per InsertionSort sortieren soll. Mein Listenelement sieht so aus:

Delphi-Quellcode:

type
  tNatZahl = 0..maxint;
  tRefListe = ^tListe;
  tListe = record
             info : tNatZahl;
             next : tRefListe;
           end;

var
  RefListe : tRefListe;

Wie soll ich denn nun aber Listenelemente vertauschen?! Ich verstehe nicht wie ich dann den Elementen ihr neues "next" zuweisen soll und das es dann sortiert wird...eiegntlich verstehe ich überhaupt nicht wie ich einen InsertionSort auf so etwas anwenden soll

Habt ihr da einen Tip für mich?

Gruß

Dragi

[Der_Unwissende]

Hi,
Insertion-Sort sagt im einfachsten Fall nichts darüber aus, dass du nur eine feste Menge von Elementen verwendest. Wenn du nicht diese explizite Einschränkung hast (dass du in-place sortieren musst), dann kannst du einfach mit zwei Listen arbeiten. Verwende einfach eine zweite sortierte Liste. Die ist am Anfang leer, dann machst du genau das, was der Insertion-Sort vorsieht, du nimmst das kleinste (größte) Element der unsortierten Liste und fügst es nun als letztes Element der bereits sortierten Liste ein.

Getauscht wird eigentlich eher bei anderen Sortierverfahren. Zum tauschen müsstest du vorallem auch den Vorgänger kennen. Wie man an den rankommt ist dabei eine Frage der Implementierung. An sich ist es aber beim Insertion-Sort nie nötig!

Gruß Der Unwissende

[r2c2]

Für was out-of-place sortieren? InsertionSort is doch geradezu gemacht dafür Verkettete Listen zu sortieren... Warum? Verschieben is bei verketteten Listen O(1), bei arrays O(n)(naja nciht ganz, das wär jetzt worst-case. Im average-case isses etwas besser). Du kannst also annähernd linear sortieren! Jedenfalls in Bezug auch die Zuweisungen[1].

Alles was du dazu brauchst is ne Move-Prozedur/Methode. Die sieht ungefähr so aus:

Delphi-Quellcode:

// Pseudocode:
// Element entfernen:
  VorherigesElement.Next := Element.Next;

// Element an der gegebenen Stelle einfügen:
  Element.Next := ElementVorRichtigerPosition.Next;
  ElementVorRichtigerPosition.Next := Element;

[1] Die Vergleiche sind da wider etwas schlechter, als bei den arrays, da der Zugriff aufwändiger ist. Da aber InsertionSort sowieso relativ wenige Vergleiche braucht, is InsertionSort in diesem Fall sehr gut geeignet...

mfg

Christian

[Der_Unwissende]

Zitat von r2c2:

Für was out-of-place sortieren?

Um die einfache Idee zu vermitteln. Es wurde doch von Dragi gesagt, dass er gar nicht weiß wie man so sortiert. Wenn jmd. das mit zwei Listen klar ist, dann ist der nächste Schritt einfach. Natürlich ist Vertauschen auf Listen einfach (wenn man es verstanden hat) und natürlich ist eine Verkettete Liste nur ein Zeiger. 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.

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.

[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

[Der_Unwissende]

Zitat von r2c2:

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).

Ich möchte mich jetzt hier gar nicht weiter über den Sinn und unsinn von in-place vs. nicht in-place streiten. Was ich sagen wollte (ein letztes mal auch sage) ist, dass die Idee einer zweiten Liste einfacher zu verstehen ist als ein zweiter Zeiger auf der gleichen Menge. Damit würde die Idee (je nach Definition) nicht in-place realisiert werden. Wie man es tatsächlich umsetzt ist dann eine andere Sache.
In-place wäre es wohl auch dann, wenn man eine zweite Liste nimmt, denn hier wird nur konstant viel mehr an Speicher gebraucht (jedes Element ist immer nur in einer der beiden Listen, egal ob real existent oder nicht). In einer verketteten Liste werden doch eh nur die Zeiger auf ein Element gespeichert, also brauch ich hier nie ein Element neu erzeugen, ich verschiebe nur den Speicher.

Wenn man sich nun die verkettete Liste als eine lineare Struktur, die hintereinander im Speicher liegt vorstellt (kann man machen, denn man folgt eh nur den Zeigern, was dazwischen im Speicher liegt interessiert uns für die Liste schließlich nicht), dann könnte man sich die Liste als eine Art Array dyn. Länge vorstellen (eine gewisse Vereinfachung, rein virtueller Natur!). Hier finde ich kann man sich leichter vorstellen mit zwei Listen zu arbeiten, als zwei Zeiger auf der gleichen Liste zu verwenden (ist nur meine Meinung).
Der Overhead einer zweiten Liste bestünde nun darin, dass man diese zwischen-speichern müsste. Man braucht also einen Zeiger auf das erste Element der Liste (und aus Bequemlichkeit einen auf das letzte Element, ermöglicht schnelles anhängen, ist aber nicht nötig). Das sind also zwei Zeiger, die man benötigt. Kling finde ich nach einem vertretbaren und vorallem konstanten Overhead.
Da hier eh nur mit Zeigern gearbeitet wird, kann ich Elemente einfach verschieben, ohne dass ich die je kopieren muss. Also brauche ich nur konstant viel mehr Speicher (ca. 8 Byte). Das wäre also (entgegen meiner ersten Behauptung) durchaus in-place, gebe ich dir Recht!

Jetzt finde ich es aber immer noch leichter, dass ich mir vorstelle, dass ich eine sortierte Liste und eine unsortierte habe. Am Anfang ist dann die sortierte Liste leer, die unsortierte voll. Jetzt durchsucht man alle Elemente der unsortierten Liste und nimmt das kleinste raus. Dies wird nun in die sortierte Liste getan. So macht man weiter. Die Frage ist also, wie nimmt man ein Element aus einer Liste heraus und wie fügt man es in eine Liste ein. Da hat r2c2 ja schon einiges zu gesagt. Wie man das letztlich realisiert ist jedoch auf mehr als eine Art und Weise möglich (wie vielleicht aus den letzten Beiträgen inkl. diesem hervor geht).

Falls der Threadsteller hier nicht auf eine einfach verkettete Liste eingeschränkt ist, so bietet sich eine doppelt verkettete Liste an, diese kennt dann auch ihren Vorgänger, dass macht das ausgliedern eines Elements leichter.

[Meniskusschaden]

Zitat von Der_Unwissende:

Jetzt finde ich es aber immer noch leichter, dass ich mir vorstelle, dass ich eine sortierte Liste und eine unsortierte habe. Am Anfang ist dann die sortierte Liste leer, die unsortierte voll. Jetzt durchsucht man alle Elemente der unsortierten Liste und nimmt das kleinste raus. Dies wird nun in die sortierte Liste getan.

Nur zur Richtigstellung: Deine Erklärung beschreibt nicht Insertion-Sort sondern Selection-Sort. Für die Diskussion pro und contra in-place dürfe das aber gleichgültig sein.

[Der_Unwissende]

Zitat von Meniskusschaden:

Zitat von Der_Unwissende:

Jetzt finde ich es aber immer noch leichter, dass ich mir vorstelle, dass ich eine sortierte Liste und eine unsortierte habe. Am Anfang ist dann die sortierte Liste leer, die unsortierte voll. Jetzt durchsucht man alle Elemente der unsortierten Liste und nimmt das kleinste raus. Dies wird nun in die sortierte Liste getan.

Nur zur Richtigstellung: Deine Erklärung beschreibt nicht Insertion-Sort sondern Selection-Sort. Für die Diskussion pro und contra in-place dürfe das aber gleichgültig sein.

Ups, stimmt!
Egal, die sind an sich aber auch nicht soweit voneinander entfernt. Leichter macht es die Sache aber irgendwie schon.

Gruß Der Unwissende