Sortieralgorithmus Insertion Sort als Code?
Ich verstehe nicht, wie der Algorithmus funktionieren soll??
Wieso wird i zu j umbenannt?
Was heißt solange j>0 und sortiert[j-1] > buecher i? Wieso das j-1 dort?
Wieso j= j-1 und was passiert bei sortiert[j]= buecher[i]
Der Algorithmus ist ein Sortier Algorithmus Insertion Sort
Bitte um Hilfee
3 Antworten
Angenommen, wir haben folgende Menge:
[ 2, 5, 3, 1 ]
Dann würde es folgend ablaufen:
- Die 2 wird an die erste Stelle der neuen Menge sortiert.
- Die 5 wird genommen und mit dem letzten Element der sortierten Menge verglichen. Ist sie größer, kommt sie an das Ende. Ist sie kleiner, ist eine Verschiebung notwendig. Logischerweise tritt der erste Fall in Kraft, die sortierte Menge sieht nun so aus: [ 2, 5 ]
- Das nächste Element (3) wird geholt und erneut mit dem letzten Element der sortierten Menge (nun 5) verglichen. Da die 3 kleiner als 5 ist, wird die 5 um eins nach rechts gerückt und die 3 davor eingeordnet. Die sortierte Menge sieht dann so aus: [ 2, 3, 5 ]
- Das letzte Element wird gepackt (1). Die ist ist kleiner als 5, 3 und 2. Diese Elemente werden also jeweils um einen Platz nach rechts verschoben, die 1 kommt an die erste Stelle.
Zusammenfassen lässt sich der Ablauf also so: Man greift sich nach und nach ein Element aus der unsortierten Liste heraus und vergleicht es mit dem letzten Element der neuen Liste.
- Wenn es noch keines gibt, wird das Element einfach an die erste Stelle verfrachtet.
- Wenn das letzte Element kleiner ist, als das gegriffene Element, kommt das gegriffene Element auf die Nachfolgeposition
- Wenn das letzte Element größer ist, geht man Schritt für Schritt so oft eine Position nach links und vergleicht mit den dortigen Elementen, bis sich das gegriffene Element einordnen lässt. Um dafür aber auch Platz zu bekommen, rücken alle größeren Elemente um eine Position nach rechts.
Wieso wird i zu j umbenannt?
Die Variable i zeigt in der Schleife immer auf die Position, die man in dem Schritt gerade aus der unsortierten Menge herausgreift (und ebenso auf die letzte Position der sortierten Menge, die einen Wert besitzt). Wenn nun der Fall auftritt, dass man durch die sortierte Menge laufen muss, um die richtige Position für die Einordnung zu finden, möchte man logischerweise diesen Wert als Startwert verwenden, aber i auch nicht verändern. Also kopiert man sich den Wert in eine neue Variable.
Um es am obigen Beispiel deutlich zu machen. Im dritten Durchlauf der Schleife hat i den Wert 2. Die 3, die an dieser Stelle liegt, ist kleiner als 5. Man muss also nun schauen, an welchen der vorherigen Plätze die 3 eingeordnet werden kann. Man kopiert sich den Wert 2 in eine neue Variable und nutzt diese sogleich als Schleifenvariable für die interne Schleife.
gehe beginnend von 2 rueckwaerts durch die Elemente der sortierten Menge, j = aktuelle Position
ist das Element an Position j groesser als das gegriffene Element?
ja: Verschiebe es nach rechts und gehe weiter (j = j - 1)
nein: Fuege das neue Element an der Stelle von j ein
Was heißt solange j>0 und sortiert[j-1] > buecher i? Wieso das j-1 dort?
Im allerersten Durchlauf ist i = 0 (und j logischerweise dann ebenso). Zu diesem Zeitpunkt ist die neue (sortierte) Menge noch leer. Es gibt also noch kein Element zum Vergleichen, stattdessen wird das gegriffene Element auf jeden Fall an die erste Position gelegt. Der Vergleich j > 0 wirkt hier also als Filter für den ersten Durchlauf.
Der zweite Vergleich:
sortiert[j - 1] > buecher[i]
wird nur durchgeführt, wenn der vorherige Filter (j > 0) passiert werden konnte. Man kann also davon ausgehen, dass es bereits n Elemente in der sortierten Liste gibt.
Zum Vergleich nehme ich einmal wieder mein obiges Beispiel und erkläre es anhand vom zweiten Schleifendurchlauf.
// aktueller Zustand:
unsortiert = [ 2, 5, 3, 1 ]
i = 1
j = 1
sortiert = [ 2 ]
sortiert[j - 1] = sortiert[0] = 2
buecher[i] = 5
j > 0 -> wahr
sortiert[j - 1] > buecher[i] = 2 > 5 -> falsch
Du siehst also: Es wird immer das letzte Element der unsortierten Liste genommen und die letztbesetzte Position in der sortierten Menge. Die Subtraktion bei dem Index (j - 1) ist nötig, da die sortierte Menge quasi immer um ein Element hinterherhinkt.
Wieso j= j-1 (...)
Diese innere Schleife (Wiederhole solange) läuft ausgehend von der letztbesetzten Position der sortierten Menge rückwärts (bzw. nach links) durch die bereits sortierten Elemente. Dafür erstellt man sich eine Variable, die die aktuelle Position innerhalb dieses Durchlaufs speichert. Sie beginnt bei der aktuellen Position der äußeren Schleife (j) und zählt dann nach unten.
(...) und was passiert bei sortiert[j]= buecher[i] (...)
Die Variable j zeigt zu diesem Zeitpunkt auf die Position, an die das gegriffene Element in der sortierten Menge gelegt werden soll (vgl. mit dem zuletzt erklärten Abschnitt). Die Variable i gibt nach wie vor die Position des herauszugreifenden Elements an. Bei dieser Zuweisung erfolgt nun das Einordnen des Elements aus der unsortierten Liste hinein in die neue, sortierte Liste.
Mein abschließender Tipp: Gib i und j bessere Namen (z.B. aktuellePosition und aktuellePositionInSortierterMenge) und spiele so ein Beispiel wie das meinige einmal selbst Schritt für Schritt durch. Mach es ruhig so, wie bei meinem obigen Snippet (aktueller Zustand).
Das ist aufwendig und verlangt Konzentration, ist aber auch notwendig, um es wirklich zu verstehen. Andererseits wird auch mein bisheriger Text schwer verständlich für dich bleiben.
Was ist das denn für eine komische Programmiersprache? wtf
Der Wert von i wird j zugewiesen, um ihn zu verändern, da man jeweils den Index des Bücher-Array und des Sortiert-Array braucht.
Wenn man dem PAP folgt, wird geschaut ob der Titel des Buchs im Regal größer ist, nebenbei wird überprüft ob j >0 ist.
(Das -1 wird wohl fü das Buch stehen, das am weitesten rechts steht)
Solange die Schleife läuft wird j verkleinert, um das Buch nach rechts zu verschieben.
Am Ende wird der Inhalt vom Bücher-Array am jeweiligen Index, dem Index in sortiert zugewiesen.
(Bei j := j -1 wird j um eins verkleinert, damit man wieder das Buch hat, dass am rechtesten im Regal steht.)
Das hätte man an sich schöner lösen können.
Es gibt nun wirklich keinen Grund Deklarationen mit := zu lösen.
Auch wäre es schöner j-- zu nutzen.
Es ist Peusdocode, der kennt gar keine Deklarationen - := orientiert sich an der math. Definition.
Entsprechend vermeidet man auch sprachspezifische Operatoren wie --var bzw. var--.
i wird nicht zu j umbenannt, sie werden gleichgesetzt. Heißt konkret j nehme der Wert von i an. Da über i iteriert wird, ist j in jedem Durchlauf ein anderer Wert.
Nimm Stift und Papier und gehe es einfach schrittweise durch.
Vereinfacht: Die innere Schleife schiebt alle bereits sortiert eingefügten Werte nach oben, bis das aktuell betrachtete buch in die vorhandene Sortierung passt, dann wird es übernommen.
Gar keine, ist einfach Pseudocode.