Algorithmen und Datenstrukturen #15 - Insertion Sort

Algorithmen machen unsere digitale Welt. In dieser Serie erfahrt ihr, wie die Dinger eigentlich funktionieren.

Nicht vergessen: Liken, Abo und ein Kommentar helfen diesem Video sehr =)

_Discord:_

_Unterstützt mich - Danke!:_

[lowfartsportbymanielplugge]

Die Komplexität lässt sich doch schon erheblich verbessern mit dem, was wir aus deinen vorherigen Videos schon kennen. Besser als O(n) kann man nicht werden, da man jedes Element mindestens einmal anschauen muss. Aber für das Einfügen in die Ergebnisliste muss man doch nicht durch jedes Element der Ergebnisliste, sondern man könnte doch mit einer binären Suche die Position bestimmen, oder? Voraussetzung für die binäre Suche war ja, dass die Liste, auf der die Suche durchgeführt wird, sortiert ist. Und das ist sie im hiesigen Fall.

[nico]

3:25 Hab mal die Bedeutung von "in-place" nachgeschaut und festgestellt, dass Insertion sort doch in-place ist! (Wikipedia)

[delta]

Das folgende hat eher nichts mit dem Video zutun aber ich würde gerne Meinungen von Leuten die sich vllt etwas mit der Materie beschäftigen :D



Ich habe seit Windows 10 kein zusätzliches Antivirus Programm auf meinem Rechner installiert. Einfach, weil ich gehört habe das es den PC nur langsamer machen würde und nichts bringt. Ich bin kein Informatiker oder so, deswegen habe ich keine Ahnung aber bisher habe ich keine schlechten Erfahrungen gemacht. Aber ich würde jetzt gerne Mal genau wissen. Die sogenannten "Experten" aus diversen Internetseiten geben dazu aber keinen wirklichen Aufschluss, weshalb ich dachte das ich mal hier nachfragen könnte :D