Diskussion:Insertionsort/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Insertionsort/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung außerhalb der Wikipedia

https://de.wikipedia.org/wiki/Diskussion:Insertionsort/Archiv/1#Thema_1

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 (nicht signierter Beitrag von 80.144.154.72 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-80.144.154.72-2004-02-19T18:30:00.000Z-pascal-code ungetestet11)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-80.144.154.72-2004-02-19T18:30:00.000Z11

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? (nicht signierter Beitrag von 217.224.89.45 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-217.224.89.45-2005-03-13T18:10:00.000Z-Stabil oder nicht stabil?11)

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 Diskussion:Insertionsort/Archiv/1#c-88.76.43.6-2007-07-02T16:19:00.000Z-217.224.89.45-2005-03-13T18:10:00.000Z11

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-217.224.89.45-2005-03-13T18:10:00.000Z11

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 (nicht signierter Beitrag von 80.133.29.74 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-80.133.29.74-2005-10-23T18:18:00.000Z-unsortiertes array->leeres zielarray11)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-80.133.29.74-2005-10-23T18:18:00.000Z11

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)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-O(n) wenn man verkettet listen verwendet11

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 Diskussion:Insertionsort/Archiv/1#c-Squizzz-2006-05-05T15:06:00.000Z-Abschnitt „Implementierung“11

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

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. (nicht signierter Beitrag von 87.161.223.131 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-87.161.223.131-2008-08-26T19:52:00.000Z-Abschnitt „Implementierung“11)

Wieso sind hier so wenige codes. Was ist mit basic usw.? (nicht signierter Beitrag von 84.148.76.118 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-84.148.76.118-2006-07-20T18:22:00.000Z-mehr code-beispiele11)

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; }

(nicht signierter Beitrag von 134.155.26.222 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-134.155.26.222-2007-06-28T19:32:00.000Z-mehr code-beispiele11)

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 (nicht signierter Beitrag von Ooops (Diskussion | Beiträge) Diskussion:Insertionsort/Archiv/1#c-Ooops-2006-11-20T10:33:00.000Z-Visual Basic11)

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 Diskussion:Insertionsort/Archiv/1#c-Squizzz-2006-11-20T12:36:00.000Z-Ooops-2006-11-20T10:33:00.000Z11

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-Ooops-2006-11-20T10:33:00.000Z11

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"? (nicht signierter Beitrag von 88.134.170.39 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-88.134.170.39-2007-07-19T19:05:00.000Z-Beispiel11)

Das liegt, soweit ich es sehe, daran, dass sowohl der Pseudocode als auch die Erklärung zum Beispiel annehmen, dass der Index des ersten Elements 1 ist, wohingegen die Indizes bei den Beispieltabellen immer bei 0 anfangen. (nicht signierter Beitrag von 84.171.91.144 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-84.171.91.144-2016-06-23T12:06:00.000Z-88.134.170.39-2007-07-19T19:05:00.000Z11)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-88.134.170.39-2007-07-19T19:05:00.000Z11

War es nicht so, dass Insertion sort speziell für <= 5 Elemente das beste Sortierverfahren ist? Ich hab gehört, dass einige Implementationen der klassischen Sortierverfahren sobald sie bei <= 5 Elementen angekommen sind, auf Insertion sort wechseln. Das ist natürlich jetzt absurd, weil irgendeiner das "mal gehört" hat, das direkt reinzuschreiben und mir fallen gerade keine Quellen ein, aber vielleicht kennen sich ja einige andere User gut aus und können das bestätigen und belegen. Wenn es nämlich so ist, wäre es sicher ein interessantes Detail. (Der Grund, warum ich auf diese Seite gekommen bin, war, dass ich das nochmal nachschauen wollte und wenn mir das passiert, passiert das bestimmt auch manchmal anderen Usern.) -- Lykos42 Diskussion:Insertionsort/Archiv/1#c-Lykos42-2010-02-15T00:21:00.000Z-Kleine Eingabemengen11

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-Lykos42-2010-02-15T00:21:00.000Z11

Das letzte Element der zu sortierenden Folge wird im Pseudocode als auch im Struktogramm nicht "angefasst". Entweder muss die zu sortierende Folge die Elemente 0,...,length(A)-1 oder 1,...,length(A) haben. So wie es im Moment da steht ist das meines Erachtens nicht korrekt! -- 16:28, 20. Apr. 2010 (CET) (ohne Benutzername signierter Beitrag von 91.43.54.15 (Diskussion | Beiträge) )

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-Pseudocode & Struktogramm11

Warum sollte man mit einer anfangs "leeren" Liste beginnen? In der Tat wird ein beliebiges Element bereits eingefügt, da ein Element für sich alleine ja bereits sortiert ist. (nicht signierter Beitrag von Scotty16 (Diskussion | Beiträge) Diskussion:Insertionsort/Archiv/1#c-Scotty16-2011-04-14T14:57:00.000Z-(anfangs leere) ausgabefolge?!11)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-Scotty16-2011-04-14T14:57:00.000Z11

Müsste man die Formel ${\displaystyle n(n+1)/2-n\in {\mathcal {O}}(n^{2})}$ nicht zu ${\displaystyle n(n-1)/2\in {\mathcal {O}}(n^{2})}$ vereinfachen können? --92.206.181.175 Diskussion:Insertionsort/Archiv/1#c-92.206.181.175-2011-07-19T11:52:00.000Z-Komplexität11

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-92.206.181.175-2011-07-19T11:52:00.000Z11

Der Vergleich mit den Spielkarten hinkt insofern, dass das sortierte Blatt nicht unbedingt kartenweise, sondern per binärer Suche (auch von Menschen) nach der passenden Einfügestelle abgesucht wird. Die binäre Suche hat die Ordnung ln(n). Ich weiß jetzt nicht, ob Insertionsort (übrigens: Deutsche Bezeichnung irreführend: Insertions-Ort) die binäre Suche der Einfügestelle inkludiert; falls ja wäre die Ordnung günstiger als n².

Und noch etwas hinkt bei dem Vergleich: Ich kann keine Bezeichnung für das Verfahren des Einfügens eines Elements in eine sortierte Liste finden! Dabei ist eine solche Funktion der Dreh- und Angelpunkt von vielen praktische implementierten GUI-Elementen, etwa Windows ComboBox mit CBS_SORT-Stilbit, siehe auch WM_COMPAREITEM.

--Henrik Haftmann (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Henrik Haftmann-2012-10-01T14:46:00.000Z-Der Vergleich hinkt11

Moin! Die hier dargestellte Version ist die Standard-Version von InsertionSort, wie sie auch in allen Lehrbüchern dargestellt wird, ebenso wie der SPielkartenvergleich. Die Suche erfolgt nicht binär, sondern linear in O(n) bei binärer Suche wäre InsertionSort (hab's jetzt aber auch nicht genau gecheckt) wohl auch nicht mehr stabil, weil die Einfügeposition nicht genau vorhergesagt werden kann. Ansonsten gilt: Das Ding ist halt nunmal so definiert ;-) und wenn Du's schnell haben willst, wirst Du wohl 'eh einen der O(n) (für bestimmte Daten) oder O(n*log(n))-Verfahren nehmen.

Was Du mit Deiner letzten Bemerkung sagen willst, verstehe ich aber nicht: Man könnte natürlich die innere Schleife durch einen Funktionsaufruf insertAt(...) ersetzen, der dann unten definiert wird, aber das macht den Code auch nicht unbedingt leserlicher. War das gemeint? --Jkrieger (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Jkrieger-2012-10-01T15:00:00.000Z-Henrik Haftmann-2012-10-01T14:46:00.000Z11

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-Henrik Haftmann-2012-10-01T14:46:00.000Z11

Der im Pseudocode gezeigte Algorithmus ist nicht korrekt.

So bleibt z.B. ein unsortiertes Array der Länge 2 unsortiert. Auch wird unter bestimmten Umständen der Wert bei A[0] nicht korrekt einsortiert. (nicht signierter Beitrag von 80.153.161.44 (Diskussion) Diskussion:Insertionsort/Archiv/1#c-80.153.161.44-2014-04-24T15:14:00.000Z-Korrektheit Pseudocode11)

Die Einträge von A sind A[1]...A[Länge(A)], wie kurz vor dem Pseudocode steht. --Daniel5Ko (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Daniel5Ko-2014-04-24T18:04:00.000Z-80.153.161.44-2014-04-24T15:14:00.000Z11

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) Diskussion:Insertionsort/Archiv/1#c-Arilou-2019-07-09T07:29:00.000Z-80.153.161.44-2014-04-24T15:14:00.000Z11