Diskussion:Insertionsort

aus Wikipedia, der freien Enzyklopädie

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

Inhaltsverzeichnis 1 Stabil oder nicht stabil? 2 O(n) wenn man verkettet listen verwendet 3 Abschnitt „Implementierung“ 3.1 Visual Basic

[Bearbeiten] 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)

//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

[Bearbeiten] 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)

[Bearbeiten] Abschnitt „Implementierung“

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.? (Der vorstehende, nicht signierte Beitrag stammt von 84.148.76.118 (Diskussion • Beiträge) 20:22, 20. Jul 2006 )

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

[Bearbeiten] 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)