InsertionSort

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

InsertionSort

Beitrag von LukasPhysiker » 9. Sep 2017 22:24

Es gibt eine Nabla Aufgabe zum InsertionSort, der nicht für die Nabla-Testate relevant war, aber für die Klausur haben wir ja keine solche Zusicherung. In der Videothek habe ich kein Video dazu gefunden, also habe ich mir dieses Youtube-Video angesehen:
https://www.youtube.com/watch?v=JMRU2nh6bfs&t=206s

Wenn ich versuche, die Aufgaben so zu lösen, funktioniert das aber nicht. Es ist auch nicht so, dass man einfach von rechts statt von links sortieren müsste. Kann mir jemand erklären, wie der InsertionSort-Algorithmus funktioniert, den Nabla benutzt?

CryNickSystems
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 30. Apr 2015 18:27

Re: InsertionSort

Beitrag von CryNickSystems » 10. Sep 2017 06:33

Die Aufgabe ist nicht allzu schwer:
Es gibt quasi einen unsortierten und einen sortierten Bereich, wie bei den anderen Sortieralgorithmen auch, wobei der sortierte Bereich zu Beginn leer ist, und rechts, neben der unsortierten Liste steht.

Du gehst In jeder Iteration die unsortierte Liste einmal von Links nach rechts durch und suchst das größte Element, bei mehreren größten Elementen wird der erste Kandidat genommen (also bei [1, 2, 2, 1] ist die erste 2 das größte Element) und schiebst diese dann an den linken Teil des sortierten Bereichs.

Ich habe mal beispielhaft eine Aufgabe als Video in Form einer GIF gelöst:
https://abload.de/img/02148956_2017-09-10_0jwr6d.gif

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: InsertionSort

Beitrag von LukasPhysiker » 10. Sep 2017 14:45

Danke, mit dieser Beschreibung konnte ich die Aufgabe lösen!

Das ganze scheint mir aber mehr eine Variante vom SelectionSort zu sein als der InsertionSort aus dem Video...

Wieder einmal ist das Problem, dass in der Aufgabe steht:
Aus der Vorlesung kennen Sie den Algorithmus "Insertionsort".
Und ich wüsste nicht, dass das jemals in der Vorlesung vorkam... Aber jetzt weiß ich ja wie es geht.

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: InsertionSort

Beitrag von LukasPhysiker » 10. Sep 2017 14:53

Übrigens: Wie ich gerade beim Testen festgestellt habe, macht es wohl für Nabla keinen Unterschied, wenn man Elemente mit den gleichen Zahlen vertauscht. Das ist auch gut so, falls man die Übersicht darüber verliert, wo die Elemente am Anfang waren. In der Klausur ist das natürlich eh egal.

Jetzt wo ich die Erklärung habe, bekomme ich auf einmal häufig den trivialen Fall, dass die gesamte Liste sortiert ist. Mein sollte meinen, dass die Entwickler von Nabla so einen Fall explizit aussschließen würden...

Antworten

Zurück zu „Archiv“