{"id":4820,"date":"2024-06-24T16:00:51","date_gmt":"2024-06-24T16:00:51","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4820"},"modified":"2026-02-17T11:32:59","modified_gmt":"2026-02-17T11:32:59","slug":"insertion-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/insertion-sort\/","title":{"rendered":"Insertion sort &#8211; Einf\u00fcgungssortierung in Java"},"content":{"rendered":"<p>Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig f\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten ben\u00f6tigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus h\u00e4ngt von Faktoren wie der Gr\u00f6\u00dfe und den Eigenschaften der Eingabedaten, dem verf\u00fcgbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erkl\u00e4ren und sie in Java programmieren. Bislang haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\" target=\"_blank\" rel=\"noopener\">Sortieralgorithmen<\/a>: eine Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\" target=\"_blank\" rel=\"noopener\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\" target=\"_blank\" rel=\"noopener\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\" target=\"_blank\" rel=\"noopener\">Big O Notation<\/a>: Analyse der Komplexit\u00e4t von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Selection sort<\/a> &#8211; triedenie v\u00fdberom.<\/li>\n<\/ul>\n<p>Heute werden wir uns die Einf\u00fcgungssortierung &#8211; <strong>Insertion sort<\/strong> ansehen.<\/p>\n<h2>Insertion sort<\/h2>\n<p>Insertion Sort ist ein einfacher und intuitiver Algorithmus zum Sortieren eines Arrays oder einer Liste von Elementen. Er funktioniert \u00e4hnlich wie die Methode, mit der Menschen Spielkarten auf ihrer Hand sortieren. Sie halten ihre erhaltenen Karten sortiert und legen jede neue Karte, die sie erhalten, an ihren Platz, um ihre relative Reihenfolge beizubehalten.<\/p>\n<h3>Insertion sort vs selection, quick, merge sort<\/h3>\n<p>Insertion Sort wird oft als Teil von komplexeren Sortieralgorithmen verwendet (z.B. f\u00fcr kleine Teilmengen in Quick Sort oder Merge Sort), da seine Leistung f\u00fcr kleine Datens\u00e4tze gut ist. Im Vergleich zu <a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Selection Sort<\/a>, das wir beim letzten Mal besprochen haben, bietet es einen stabilen Algorithmus.<\/p>\n<h2>Insertion sort algoritmus &#8211; Funktionsprinzip<\/h2>\n<p>Der Algorithmus beginnt mit der Aufteilung des Eingabevektors in einen sortierten und einen unsortierten Teil. Das erste Element des Arrays wird automatisch als sortiert betrachtet und die restlichen Elemente m\u00fcssen noch sortiert werden. F\u00fcr jedes Element im unsortierten Teil (vom zweiten bis zum letzten Element des Arrays) wird dieses Element ausgew\u00e4hlt und an der richtigen Stelle in den sortierten Teil des Arrays eingef\u00fcgt, so dass der sortierte Teil weiterhin geordnet ist. Bei diesem Schritt wird das ausgew\u00e4hlte Element mit den anderen Elementen im sortierten Teil verglichen und die Elemente werden neu angeordnet, um Platz f\u00fcr das ausgew\u00e4hlte Element zu schaffen. Das Umordnen kann vermieden werden, wenn wir einen Listen-Datentyp anstelle eines Arrays w\u00e4hlen.<\/p>\n<p>Anschlie\u00dfend werden wir ein praktisches Beispiel in Java-Code zeigen.<\/p>\n<h2>Vorteile des Sortieralgorithmus Insertion<\/h2>\n<ul>\n<li>Leicht zu verstehen und umzusetzen,<\/li>\n<li>effizient f\u00fcr kleine Datens\u00e4tze oder nahezu geordnete Arrays,<\/li>\n<li>geeignet f\u00fcr eingehende Elemente, die kontinuierlich sortiert werden m\u00fcssen,<\/li>\n<li>ben\u00f6tigt keinen zus\u00e4tzlichen Speicher f\u00fcr die Sortierung,<\/li>\n<li>stabil.<\/li>\n<\/ul>\n<h2>Nachteil des Sortieralgorithmus Insertion<\/h2>\n<ul>\n<li>Die Zeitkomplexit\u00e4t ist jedoch immer noch O(n\u00b2), was ihn zu einem langsamen Algorithmus f\u00fcr einen gro\u00dfen Datensatz macht.<\/li>\n<\/ul>\n<h2>Intensit\u00e4t der Einf\u00fcgezeit<\/h2>\n<table width=\"496\">\n<thead>\n<tr>\n<th rowspan=\"2\" width=\"87\"><strong>Algorithmus<\/strong><\/th>\n<th rowspan=\"2\" width=\"77\"><strong>Methode<\/strong><\/th>\n<th colspan=\"3\" width=\"192\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th rowspan=\"2\" width=\"76\"><strong>Speicher<\/strong><\/th>\n<th rowspan=\"2\" width=\"64\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr>\n<th width=\"68\"><strong>schlechteste<\/strong><\/th>\n<th width=\"59\"><strong>durchschnittlich<\/strong><\/th>\n<th width=\"65\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td width=\"87\">Insertion sort<\/td>\n<td width=\"77\">einbetten.<\/td>\n<td width=\"68\">O(n\u00b2)<\/td>\n<td width=\"59\">O(n\u00b2)<\/td>\n<td width=\"65\">n<\/td>\n<td width=\"76\">O(1)<\/td>\n<td width=\"64\">Ja<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Insertion sort Animation, Visualisierung, gif<\/h2>\n<p>Die Visualisierung der Insertion sort sieht wie folgt aus:<\/p>\n<figure id=\"attachment_3635\" aria-describedby=\"caption-attachment-3635\" style=\"width: 300px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-3633 size-medium\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/06\/Insertion-sort-example-300x180.gif\" alt=\"Visualisierung des Insertion-Sort-Verfahrens \" width=\"300\" height=\"180\" \/><figcaption id=\"caption-attachment-3635\" class=\"wp-caption-text\">Swfung8, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<figure id=\"attachment_3647\" aria-describedby=\"caption-attachment-3647\" style=\"width: 193px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-3645 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/06\/Insertion_sort.gif\" alt=\"Insertion sort Visualisierung\" width=\"193\" height=\"302\" \/><figcaption id=\"caption-attachment-3647\" class=\"wp-caption-text\">Simpsons Mitwirkender, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<p><em>Quelle: commons.wikimedia.org\/wiki\/Category:Animations_of_sort_algorithms<\/em><\/p>\n<p>Eine Animation des Algorithmus findest du z.B. auf <a href=\"https:\/\/www.toptal.com\/developers\/sorting-algorithms\" target=\"_blank\" rel=\"nofollow noopener\">Toptal.<\/a> Es gibt 8 Arten von Algorithmen, du kannst die Animation auch r\u00fcckw\u00e4rts abspielen. Auf dieser <a href=\"https:\/\/www.hackerearth.com\/practice\/algorithms\/sorting\/insertion-sort\/visualize\/\" target=\"_blank\" rel=\"nofollow noopener\">Seite<\/a> kannst du die Schritte des Algorithmus durchlaufen, so dass diu den Zeitaufwand des Algorithmus \u00fcberpr\u00fcfen kannst.<\/p>\n<h2>Insertion sort Implementierung, Java-Code<\/h2>\n<p>Wir werden nun eine einfache Implementierung des Insertion-Sortieralgorithmus in Java zeigen.<\/p>\n<p><strong><u>InsertionSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\npublic class InsertionSort {\n    private int key, j;\n\n    public void sort(int data[])\n    {\n        \/\/ Start with 2nd element, as 1st is considered to be sorted\n        for (int i = 1; i &lt; data.length - 1; i++) {\n            System.out.println(i + &quot;. iteration (key = &quot; + data[i] + &quot;)&quot;);\n            \/\/ Element that needs to be inserted into sorted part\n            key = data[i];\n            j = i - 1;\n            \/\/ Move all elements &gt; key one position to the right\n            while (j &gt;= 0 &amp;&amp; key &lt; data[j]) {\n                data[j + 1] = data[j];\n                j--;\n            }\n            \/\/ Insert the key in its correct spot\n            data[j + 1] = key;\n            printArray(data);\n        }\n    }\n\n    \/\/ Function to print an array\n    public void printArray(int data[])\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n        System.out.println();\n    }\n}<\/code><\/pre>\n<p>&nbsp;<\/p>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.InsertionSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };\n        InsertionSort insertionSort = new InsertionSort();\n        System.out.print(&quot;Input: &quot;);\n        insertionSort.printArray(dataToSort);\n        insertionSort.sort(dataToSort);\n        System.out.print(&quot;Sorted: &quot;);\n        insertionSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-medium wp-image-3642\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/06\/vystup-z-prikladu-insertion-sort-510-595-257x300.webp\" alt=\"Die Ausgabe dieses Beispiels ist:\" width=\"257\" height=\"300\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/06\/vystup-z-prikladu-insertion-sort-510-595-257x300.webp 257w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/06\/vystup-z-prikladu-insertion-sort-510-595.webp 510w\" sizes=\"auto, (max-width: 257px) 100vw, 257px\" \/><\/p>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade den <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/06\/InsertionSort.zip\" target=\"_blank\" rel=\"noopener\">Java Insertion Sort Code<\/a> herunter.<\/p>\n<p>Wenn du ein <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/java-entwickler-senior\/\" target=\"_blank\" rel=\"noopener\">Java Programmierer<\/a> bist und nach Arbeit suchst, schau dir unsere <a href=\"https:\/\/msg-life.sk\/de\/mitarbeiter-benefits\/\" target=\"_blank\" rel=\"noopener\">Mitareiterbenefits <\/a> an und reagiere auf die <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/\" target=\"_blank\" rel=\"noopener\">neuesten Stellenangebote<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erf\u00e4hrst du, was Insertion sort ist, sein Prinzip, seine Vorteile, seine Nachteile und ein Beispiel f\u00fcr Java-Code.<\/p>\n","protected":false},"author":14,"featured_media":3638,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[57],"tags":[],"class_list":["post-4820","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4820","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/comments?post=4820"}],"version-history":[{"count":4,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4820\/revisions"}],"predecessor-version":[{"id":9710,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4820\/revisions\/9710"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/3638"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4820"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4820"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4820"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}