Übung 4: Insertion Sort

Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x auf Blatt Nr. y lassen Sie Ihr Betreff bitte mit "y.x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Janosch
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 17. Mär 2014 14:28

Übung 4: Insertion Sort

Beitrag von Janosch » 20. Jun 2016 13:24

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ß

Max_S
Erstie
Erstie
Beiträge: 14
Registriert: 16. Apr 2015 17:09

Re: Übung 4: Insertion Sort

Beitrag von Max_S » 22. Jun 2016 21:16

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?

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übung 4: Insertion Sort

Beitrag von Prof. Karsten Weihe » 23. Jun 2016 04:59

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

Max_S
Erstie
Erstie
Beiträge: 14
Registriert: 16. Apr 2015 17:09

Re: Übung 4: Insertion Sort

Beitrag von Max_S » 23. Jun 2016 15:58

Vielen Dank für die Antwort! :)

Antworten

Zurück zu „AuD: Theoretische Aufgaben“