Seite 1 von 1

Übung 4: Insertion Sort

Verfasst: 20. Jun 2016 13:24
von Janosch
Hallo,

ich habe weder in den Folien der Vorlesung, noch in den Aufzeichnungen einen Bezug zu Insertion Sort gefunden. Lediglich einen Algowiki Eintrag. In Nabla scheint der Algorithmus nicht so ganz mit der Invariante aus dem Algowiki zu harmonieren.

Habe ich etwas übersehen oder ist die Implementation irrelevant sofern man die grobe Funktionsweise kennt?


Gruß

Re: Übung 4: Insertion Sort

Verfasst: 22. Jun 2016 21:16
von Max_S
Mir ist beim arbeiten mit Nabla und beim Ansehen der Implementation aufgefallen, dass Insertion Sort ähnlich wie Bubble Sort funktioniert? Sind diese Sortieralgorithmen etwa identisch?

Re: Übung 4: Insertion Sort

Verfasst: 23. Jun 2016 04:59
von Prof. Karsten Weihe
Max_S hat geschrieben:Mir ist beim arbeiten mit Nabla und beim Ansehen der Implementation aufgefallen, dass Insertion Sort ähnlich wie Bubble Sort funktioniert? Sind diese Sortieralgorithmen etwa identisch?
Nicht ganz.

Die äußere Schleife hat bei beiden dieselbe Invariante, grob formuliert: Nach \(i\geq 0\) Iterationen sind die \(i\) größten Elemente an den richtigen (nämlich letzten) Positionen. Nur wie das jeweils nächste Element durch die innere Schleife an seine Position kommt, ist unterschiedlich.

KW

Re: Übung 4: Insertion Sort

Verfasst: 23. Jun 2016 15:58
von Max_S
Vielen Dank für die Antwort! :)