Diskussion:Insertionsort

Der Pascal Quellcode ist leider nicht getestet, da ich momentan etwas wenig Zeit habe und mich auf eine Klausur vorbereiten muss. Daher würde es mich freuen wenn das mal jemand übernehmen könnte bzw. eventuell auch Fehler korriegieren und Ergänzungen vornehmen würde.

MfG Micha

Stabil oder nicht stabil?

Unter Sortierverfahren wird bei Insertionsort angegeben, es sei stabil. Hier im Thema um Insertionsort wird jedoch von einer Ausgabemenge gesprochen, demnach also nicht stabil. Mit einer Ausgabemenge müsste also der Speicherbedarf in O(n) (genauer: eigentlich ja genau "n") sein.

Was stimmt nun?

Stabiles Sortierverfahren bedeutet nur, dass sich beim Sortieren die Reihenfolge von zwei Objekten, die bzgl. der Vergleichsoperation gleich sind nicht ändert: Befindet sich z.B. a₁ vor dem Sortieren vor a₂ und gilt a₁=a₂, so muss sich a₁ auch nach dem Sortieren boch vor a₂ befinden. --Squizzz 01:29, 21. Mär 2005 (CET)

Der Speicherbedarf sollte aus dem Pseudocode ersichtlich sein. Insbesondere ist er O(1). --Squizzz 01:29, 21. Mär 2005 (CET)

Ich nehme an, der Fragesteller meinte nicht "stabil" sondern "in-place". Wenn eine leere Ausgabemenge gefüllt wird, arbeitet Insertion Sort ja tatsächlich nicht inplace, allerdings sind die üblichen Implementierungen (mit dem Verschieben der restlichen Elemente) ja dann doch in-place. 88.76.43.6 18:19, 2. Jul. 2007 (CEST)

//Im Bezug auf folgenden Link könnte vielleicht die Aussage, dass das unsortierte Array in ein leeres Zielarray überführt wird, überarbeitet werden? http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insertion.htm Gruß Tobsen

O(n) wenn man verkettet listen verwendet

ist diese methode nicht O(n), wenn man eine verkettete liste (mit pointern) verwendet? da muesste man die objekte ja nicht mehr verschieben.. Liste_(Datenstruktur)

--AMan 16:15, 5. Jan 2006 (CET)

Antwort: Auch in diesem Fall werden die Objekte verschoben, und zwar indem man die Zeiger ändert. Das Ändern der Zeiger ist dann wieder eine Operation. (Ich hoffe, das reicht als Erklärung.) --Squizzz 17:46, 6. Jan 2006 (CET)

Abschnitt „Implementierung“

Prinzipiell halte ich die Darstellung als Pseudocode für völlig ausreichend. Allerdings erschließt sich mir nicht, warum hier keine übliche informatische Sicht gepflegt wird, bei der Index bei 0 beginnt. Dies gilt i.Ü. für den gesamten Artikel.

Es ist nicht sinnvoll in diesen Artikel noch weitere Implementierung einzufügen, die Arrays mit Zahlen sortieren. Deren Wert ist ziemlich gering. Oder wer sortiert Zahlen in einem Array mit Insertion Sort in einer Anwendung in beispielsweise Visual Basic? --Squizzz 21:56, 19. Mär 2006 (CET)

Ich plädiere dafür den kompletten Abschnitt mit Implementierungen zu löschen. An Hand des Pseudocodes ist der Algorithmus vollständig beschrieben. Wer ihn verwenden will, sollte sich eh eher eine entsprechende Bibliothek suchen, die nach Möglichkeit auch intensiv getestet wurde. Des Weitere gibt es wohl keine, nicht willkürliche Grenze, welche Programmiersprachen man aufnimmt und welche nicht. Dadurch fällt es irgendwann schwer die Korrektheit des Artikels vernünftig zu überwachen, außer alle Code-Snippets sind auch in anerkannter Literatur veröffentlicht. --Squizzz 17:06, 5. Mai 2006 (CEST)

Der Abschnitt wurde von mir gelöscht, da niemand dafür eingetreten ist, ihn zu erhalten. --Squizzz 20:35, 20. Jul 2006 (CEST)

Wieso sind hier so wenige codes. Was ist mit basic usw.? (nicht signierter Beitrag von 84.148.76.118 (Diskussion) 20:22, 20. Jul 2006)

Siehe Eintrag oben. --Squizzz 20:35, 20. Jul 2006 (CEST)

hallo, ich habe den pseudocode entsprechend dieser Vorstellung implementiert und dieser funktioniert nicht. hier die Implementierung:

//implementierung nach vorgegebenem pseudocode ------------

public static int[] insertionSort2(int[] array) { for(int j=2;j<array.length;j++) { int speicher=array[j]; int i=j-1; while(i>0 && array[i]>speicher) { array[i+1]=array[i]; i=i-1; } array[i+1]=speicher; } return array; }

//---------------------------------------------------------

Visual Basic

Hallo Squizzz,

ich habe hier doch noch einmal ein VB-Beispiel eingefügt, welches ich selbst in VBA für Excel benötige. Ich würde freundlichst vorschlagen, das Beispiel zu belassen, damit auch Anfänger sich nicht durch die häufig nur gehobenen Ansprüchen genügende Informatik-Abteilung der Wiki abgeschreckt fühlen. Es ist getestet; Du kannst es selbst in Deinem Office (z.B. Excel-VBA-Modul) ausprobieren oder es zu einem Dialekt einer anderen Basic-Umgebung abwandeln.

Übrigens finde ich die Beschreibung unter "Prinzip" sehr irreführend: Es gibt doch gar keine separate Ausgabemenge hier, abgesehen von einem Hilfsfeld 0! Eigentlich ist das Insertionsverfahren doch nur ein multipler, intelligenter Swap.

Viele Grüße ooops

Ich habe es wieder raus. Die Wikipedia ist keine Quellcodesammlung oder ähnliches. Dafür gibt es Projekte wie Sourceforge und viele weitere. Des Weiteren habe ich kein Office *g*. Ein Anfänger wird sich meines Erachtens mit dem Pseudocode leichter tun, als mit dem Visual-Basic-Code. Dass du das VB-Beispiel benötigst ist auch kein Grund, dass es in die Wikipedia soll. (By the way: warum nutzt du keine fertige Bibliothek mit effizienteren Algorithmen?). Hast du noch ein weiteres Argument. Um den zweiten Teil deines Posting kümmere ich mich noch. Da ist der Artikel in der Tat mangelhaft. --Squizzz 13:36, 20. Nov. 2006 (CET

Beispiel

Hallo, ich finde, das Beispiel ist ein wenig irreführend, da es nicht genau dem Algorithmus folgt. Im Pseudocode beginnt die Schleife doch erst bei "j=2", im Beispiel ist dem nicht so: Warum beginnt der Algorithmus mit der "3"?

Bildbeschreibung fehlt bei [[Bild:Insertionsort-Struktogramm.png]]

Der Artikel enthält ein Bild, dem eine Bildbeschreibung fehlt, überprüfe bitte, ob es sinnvoll ist, diese zu ergänzen. Gerade für blinde Benutzer ist diese Information sehr wichtig. Wenn du dich auskennst, dann statte bitte das Bild mit einer aussagekräftigen Bildbeschreibung aus. Suche dazu nach der Textstelle [[Bild:Insertionsort-Struktogramm.png]] und ergänze sie.

Wenn du eine fehlende Bildbeschreibung ergänzen willst, kannst du im Zuge der Bearbeitung folgende Punkte prüfen:

• Namensraum Datei: Bilder sollte im Namensraum Datei liegen. Bitte ändere die alten Bezeichnungen Bild: und Image: in Datei:.
• Skalierung: Außerhalb von Infoboxen sollten keine festen Bildbreiten (zum Beispiel 100px) verwendet werden. Für den Fließtext im Artikelnamensraum gibt es Thumbnails in Verbindung mit der automatischen Skalierung. Um ein Bild/eine Grafik in besonderen Fällen dennoch größer oder kleiner darzustellen, kann der „upright“-Parameter verwendet werden. Damit erfolgt eine prozentuale Skalierung, die sich an den Benutzereinstellungen orientiert. --SpBot 22:59, 1. Mär. 2009 (CET)