Kommentare zu: Insertion Sort – Algorithmus, Quellcode, Zeitkomplexität

Von: Sven Woltmann

Sven Woltmann — Mon, 05 Dec 2022 11:15:08 +0000

Als Antwort auf Charly.

Hallo Charly,

im Average Case stand das erste 1/2 dafür, dass wir sozusagen ein Dreieck aus dem Viereck ausschneiden. Und das zweite 1/2 dafür, dass wir das zu verschiebene Element im Durchschnitt bis zur Mitte der Linie verschieben.

Im Worst Case bleibt das erste 1/2 unverändert bestehen. Das zweite 1/2 fällt aber weg, da wir jetzt das zu verschiebene Element immer bis ganz nach links schieben müssen.

Viele Grüße
Sven

Von: Thomas Seyfarth

Thomas Seyfarth — Sun, 04 Dec 2022 21:34:25 +0000

Als Antwort auf Charly.

Hallo Charly,
hier geht es um den Durchschnittlichen Fall. In diesem, wie das Chart zeigt müssen lediglich 15, statt der 30 Elemente getauscht werden also mal 1/2.

Siehe in den Abschnitt des Worst-Case:
Zitat:
"Sechs Elemente mal fünf Verschiebe-Schritte; geteilt durch zwei, da im Durchschnitt über alle Schritte die Hälfte der Karten bereits sortiert ist; und nochmal geteilt durch zwei, da das einzusortierende Element im Durchschnitt bis zur Mitte der bereits sortierten Elemente geschoben werden muss:"

Von: Charly

Charly — Wed, 09 Jun 2021 09:34:37 +0000

Super Erklärungen. Ich verstehe nur eine Sache nicht: Wofür genau steht das " *1/2 " bei der Aufwandsanalyse im Worst Case? Beim Average Case ist es toll erklärt, wofür was genau steht.

Von: Sven Woltmann

Sven Woltmann — Fri, 19 Mar 2021 09:21:03 +0000

Als Antwort auf Gabriel.

Hallo Gabriel,

Insertion Sort ist sehr einfach, deshalb ist der Quelltext sehr kurz. Und er ist vollständig.

Außerdem enthält der Artikel einen Link zu lauffähigem Beispielcode in GitHub.

Von: Gabriel

Gabriel — Fri, 19 Mar 2021 07:42:01 +0000

Das ist viel zu wenig Quelltext. Ich möchte das einfach nur Kopieren und in mein Programm einfügen, aber das ist nicht die vollendet Version. Sehr enttäuschend!!! Ich bin sehr traurig.