BucketSort-Infografik

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

BucketSort-Infografik

Beitrag von lkbaerenfaenger »

Hallo,

als Vorbereitung auf die anstehende Übung habe ich eine Infografik zum BucketSort-Algorithmus erstellt, die ich unter folgendem Link zur Verfügung stelle (Datei war zu groß, um sie anzuhängen). Ich würde mich freuen, wenn der ein oder andere sie sich mal ansehen würde - vielleicht hilft sie jemandem oder jemand entdeckt einen Fehler.

http://baerenfaenger.eu/tu/bucketsort.png

Explizit habe ich eine Frage: Die Abbruchbedingung ist laut Wiki i = N. N ist in meinem Beispiel 4. Trotzdem musste ich eine 4. Iteration durchführen, sonst hätte ein Wort im Resultat gefehlt. Ist das ein Fehler von mir, oder ist es einfach standardmäßig so, dass man, wenn i=N die Abbruchbedingung ist, die N-te Iteration noch durchlaufen lässt?

LG Lucas

jw.
Erstie
Erstie
Beiträge: 12
Registriert: 20. Apr 2013 11:54

Re: BucketSort-Infografik

Beitrag von jw. »

lkbaerenfaenger hat geschrieben:
Explizit habe ich eine Frage: Die Abbruchbedingung ist laut Wiki i = N. N ist in meinem Beispiel 4. Trotzdem musste ich eine 4. Iteration durchführen, sonst hätte ein Wort im Resultat gefehlt. Ist das ein Fehler von mir, oder ist es einfach standardmäßig so, dass man, wenn i=N die Abbruchbedingung ist, die N-te Iteration noch durchlaufen lässt?
Würde mich auch mal interessieren, hatte das gleiche Dilemma :-D
Ich habe deshalb i mit 0 initialisiert, damit man den letzten Eintrag noch nach S´ bekommt.
Ist es nicht auch so, das wenn man i mit 1 initialisiert, das dann schon vor der ersten Iteration die Invariante nicht gilt?
Denn dann würde ja vor der ersten Iteration lt. Invariante Strings der Länge [N-i+1] , also N, bereits in S´ stehen, der längste Inputstring wäre demnach schon vor der ersten Iteration in S´ was ja Schwachsinn ist?
Andererseits bekommt man in der ersten Iteration einen out-of-bounds wenn man i mit 0 initialisiert (lt. Induction step, abstract view 1) :x

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: BucketSort-Infografik

Beitrag von tmuecksch »

Same confusion here ... :shock:

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: BucketSort-Infografik

Beitrag von JannikV »

Hi,

also in der ersten Iteration ist i = 1. Insgesamt sind N Iterationen notwendig. Die N-te Iteration muss durchaus auch noch durchgeführt werden.

Die Invariante ist allerdings auch vor der ersten Iteration erfüllt. Guck dir das nochmal genau an.

Sorry, wenn jetzt nicht alles klar geworden ist bitte nochmal konkret nachfragen. Ich bin gerade schwer verwirrt xD

VG

s1mstar
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 18. Apr 2013 14:26

Re: BucketSort-Infografik

Beitrag von s1mstar »

Hallo,


kann es sein, dass im Wiki ein Fehler bei der Abbruchbedingung ist: i = N und müsste dies nicht eigentlich i = N+1 sein? Sprich genau nach der N-ten Iteration soll der Algorithmus ja abbrechen - So wie die ich die Abbruchbedingung verstehe bricht der Algorithmus hier jedoch vor der N-ten Iteration ab.

Naja obwohl - Kann natürlich auch sein, dass die Variante schon vor dem Induktionsschritt vollzogen wird. So dürfte es dann doch stimmen, wenn ich nicht ebenfalls verwirrt bin. -> Wäre dann jedoch hilfreich wenn man beim Induktionsanfang erwähnen würde, dass i auf 0 initialisiert wird.

Edit: Ich dürfte Recht haben. Bitte um Korrektur, falls dem nicht so ist. :D


Liebe Grüße,
Simon

lkbaerenfaenger
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 13. Mär 2012 12:44

Re: BucketSort-Infografik

Beitrag von lkbaerenfaenger »

s1mstar hat geschrieben:kann es sein, dass im Wiki ein Fehler bei der Abbruchbedingung ist: i = N und müsste dies nicht eigentlich i = N+1 sein? Sprich genau nach der N-ten Iteration soll der Algorithmus ja abbrechen
So habe ich es in meiner Infografik gelöst, und JannikV meint ja auch, dass es so richtig sei... :idea:

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: BucketSort-Infografik

Beitrag von R_Egert »

Hallo zusammen,

Ich glaube nicht dass das wirklich ein Fehler im Wiki ist...

Die Beschreibung von Bucketsort im Wiki gibt ja eigentlich nur eine abstrakte Beschreibung sowohl für die Theorie als auch die Implementierung. Wie das also exakt implementiert ist, is also dem Programmierer überlassen. Somit würde z.B mit i = N die letzte Iteration durchgeführt und evtl direkt danach terminiert der Algo ohne nochmals i++ auszuführen.

Viele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: BucketSort-Infografik

Beitrag von Prof. Karsten Weihe »

R_Egert hat geschrieben: Die Beschreibung von Bucketsort im Wiki gibt ja eigentlich nur eine abstrakte Beschreibung sowohl für die Theorie als auch die Implementierung. Wie das also exakt implementiert ist, is also dem Programmierer überlassen. Somit würde z.B mit i = N die letzte Iteration durchgeführt und evtl direkt danach terminiert der Algo ohne nochmals i++ auszuführen.
Das i ist eine mathematische Variable, keine programmiertechnische. Denn die Invariante und die Variante sind keine Programmieranweisungen, sondern (halb-)mathematische Aussagen. Denken Sie sich die Invariante in folgender vertrauter Form:

\(\forall i\geq 0:\ldots\).

Klarer geworden?

KW

Antworten

Zurück zu „Archiv“