{"id":12209,"date":"2020-06-25T09:00:00","date_gmt":"2020-06-25T07:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12209"},"modified":"2025-06-12T09:23:33","modified_gmt":"2025-06-12T07:23:33","slug":"selection-sort","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/selection-sort\/","title":{"rendered":"Selection Sort \u2013 Algorithmus, Quellcode, Zeitkomplexit\u00e4t"},"content":{"rendered":"\n<p>Dieser Artikel ist Teil der Serie&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/sortieralgorithmen\/\">\u201eSortieralgorithmen: Ultimate Guide\u201c<\/a>&nbsp;und\u2026<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>beschreibt wie Selection Sort funktioniert,<\/li>\n\n\n\n<li>zeigt den Java-Quellcode f\u00fcr Selection Sort,<\/li>\n\n\n\n<li>leitet die Zeitkomplexit\u00e4t her (ohne komplizierte Mathematik)<\/li>\n\n\n\n<li>und \u00fcberpr\u00fcft, ob die Performance der Java-Implementierung mit dem erwarteten Laufzeitverhalten \u00fcbereinstimmt.<\/li>\n<\/ul>\n\n\n\n<p>Die Quellcodes der gesamten Artikelserie findest du in meinem&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\" target=\"_blank\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe title=\"Selection Sort Algorithmus [Einfach erkl\u00e4rt, Deutsch]\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/FbNIp2eTs30?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"beispiel-sortieren-von-spielkarten\">Beispiel: Sortieren von Spielkarten<\/h2>\n\n\n\n<p>Das Einsortieren von Spielkarten auf die Hand ist eigentlich das klassische <a href=\"\/de\/algorithmen\/insertion-sort\/#Beispiel_Sortieren_von_Spielkarten\">Beispiel f\u00fcr <em>Insertion<\/em> Sort<\/a>.<\/p>\n\n\n\n<p>Selection Sort kann man im Grunde genommen auch mit Spielkarten darstellen. Ich kenne zwar niemanden, der seine Karten so aufnimmt, aber als Beispiel eignet es sich ganz gut ;-)<\/p>\n\n\n\n<p>Hier legst du zun\u00e4chst alle deine Karten offen vor dich auf den Tisch. Dann suchst du die kleinste Karte und nimmst sie nach links auf die Hand, danach die n\u00e4chst gr\u00f6\u00dfere und setzt sie rechts daneben, usw. bis du zuletzt die gr\u00f6\u00dfte Karte aufnimmst und ganz rechts einsortierst.<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1480\" height=\"635\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example.png\" alt=\"Selection Sort Beispiel mit Spielkarten\" class=\"wp-image-14060\" style=\"width:740px;height:318px\" title=\"\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example.png 1480w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-224x96.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-336x144.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-504x216.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-672x288.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-400x172.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-600x257.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-800x343.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-944x405.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_playing_card_example-1200x515.png 1200w\" sizes=\"(max-width: 1480px) 100vw, 1480px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"unterschied-zu-insertion-sort\">Unterschied zu Insertion Sort<\/h3>\n\n\n\n<p>Bei Insertion Sort hatten wir die jeweils n\u00e4chste unsortierte Karte genommen und dann in den sortierten Karten an der richtigen Stelle <em>eingef\u00fcgt<\/em> (\"inserted\").<\/p>\n\n\n\n<p>Selection Sort funktioniert gewisserma\u00dfen anders herum: Wir <em>w\u00e4hlen <\/em>(\"select\") die jeweils kleinste Karte aus den unsortierten Karten, um diese dann \u2013 eine nach der anderen \u2013 an die bereits sortierten Karten anzuh\u00e4ngen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"selection-sort-algorithmus\">Selection Sort Algorithmus<\/h2>\n\n\n\n<p>Der Algorithmus l\u00e4sst sich am einfachsten an einem Beispiel erkl\u00e4ren. Im folgenden zeige ich, wie man das Array [6, 2, 4, 9, 3, 7] mit Selection Sort sortiert:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Schritt 1<\/h4>\n\n\n\n<p>Wir teilen das Array gedanklich in einen linken, sortierten Teil und einen rechten, unsortierten Teil. Der sortierte Bereich ist zu Beginn leer:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"800\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1.png\" alt=\"Selection Sort Algorithmus - Schritt 1\" class=\"wp-image-14281\" style=\"width:579px;height:400px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-224x155.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-336x232.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-504x348.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-672x464.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-400x276.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-600x415.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-800x553.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithmus_schritt1-944x652.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Schritt 2<\/h4>\n\n\n\n<p>Wir suchen im rechten, unsortierten Teil nach dem kleinsten Element. Dazu merken wir uns zun\u00e4chst das erste Element, die 6. Wir gehen zum n\u00e4chsten Feld, dort finden wir mit der 2 ein noch kleineres Element. Wir wandern \u00fcber den Rest des Arrays auf der Suche nach einem noch kleineren Element. Da wir keines finden, bleibt es bei der 2. Diese setzen wir an die korrekte Position, indem wir sie mit dem Element auf dem ersten Platz tauschen. Im Anschluss schieben wir die Grenze zwischen den Array-Bereichen um eine Position nach rechts:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2.png\" alt=\"Selection Sort Algorithmus - Schritt 2\" class=\"wp-image-14211\" style=\"width:579px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-336x221.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-504x331.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-672x441.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-400x263.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-600x394.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-800x525.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step2-944x620.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Schritt 3<\/h4>\n\n\n\n<p>Wir suchen erneut im rechten, unsortierten Teil nach dem kleinsten Element. Dieses mal ist es die 3; wir tauschen sie mit dem Element an der zweiten Position:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3.png\" alt=\"Selection Sort Algorithmus - Schritt 3\" class=\"wp-image-14213\" style=\"width:579px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-336x221.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-504x331.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-672x441.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-400x263.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-600x394.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-800x525.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step3-944x620.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Schritt 4<\/h4>\n\n\n\n<p>Erneut suchen wir nach dem kleinsten Element im rechten Bereich. Es ist die 4. Diese befindet sich bereits an der richtigen Position, so dass hier keine Tauschoperation stattfinden muss und wir lediglich die Bereichsgrenze verschieben:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"760\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4.png\" alt=\"Selection Sort Algorithmus - Schritt 4\" class=\"wp-image-14216\" style=\"width:579px;height:380px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-224x147.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-336x221.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-504x331.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-672x441.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-400x263.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-600x394.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-800x525.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step4-944x620.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Schritt 5<\/h4>\n\n\n\n<p>Als kleinstes Element finden wir die 6 und tauschen sie mit dem Element am Anfang des rechten Teils, der 9:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"786\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5.png\" alt=\"Selection Sort Algorithmus - Schritt 5\" class=\"wp-image-14218\" style=\"width:579px;height:393px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-224x152.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-336x228.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-504x342.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-672x456.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-400x272.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-600x407.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-800x543.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step5-944x641.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Schritt 6<\/h4>\n\n\n\n<p>Von den verbleibenden zwei Elementen ist die 7 am kleinsten, wir vertauschen sie mit der 9:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"786\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6.png\" alt=\"Selection Sort Algorithmus - Schritt 6\" class=\"wp-image-14220\" style=\"width:579px;height:393px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-224x152.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-336x228.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-504x342.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-672x456.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-400x272.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-600x407.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-800x543.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step6-944x641.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h4 class=\"wp-block-heading\">Algorithmus beendet<\/h4>\n\n\n\n<p>Das letzte Element ist automatisch das gr\u00f6\u00dfte und damit an der richtigen Position. Der Algorithmus ist beendet, und die Elemente sind fertig sortiert:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1158\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7.png\" alt=\"Selection Sort Algorithmus - Beendet\" class=\"wp-image-14222\" style=\"width:579px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7.png 1158w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-224x142.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-336x212.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-504x319.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-672x425.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-400x253.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-600x379.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-800x506.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_algorithm_step7-944x597.png 944w\" sizes=\"(max-width: 1158px) 100vw, 1158px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"selection-sort-java-quellcode\">Selection Sort Java Quellcode<\/h2>\n\n\n\n<p>In diesem Abschnitt findest du eine einfache Java-Implementierung von Selection Sort.<\/p>\n\n\n\n<p>Die \u00e4u\u00dfere Schleife iteriert \u00fcber die einzusortierenden Elemente und endet nach dem vorletzten Element. Wenn dieses sortiert ist, ist automatisch auch das letzte Element sortiert. Die Schleifenvariable&nbsp;<code>i<\/code>&nbsp;zeigt immer auf das erste Element des rechten, unsortierten Teils.<\/p>\n\n\n\n<p>Als kleinstes Element <code>min<\/code> wird in jedem Schleifendurchlauf zun\u00e4chst das erste Element des rechten Teils angenommen; dessen Position wird in <code>minPos<\/code> gespeichert.<\/p>\n\n\n\n<p>Die innere Schleife iteriert dann vom zweiten Element des rechten Teils bis zu dessen Ende und weist <code>min<\/code> und <code>minPos<\/code> immer dann neu zu, wenn ein noch kleineres Element gefunden wird.<\/p>\n\n\n\n<p>Nach dem Durchlauf der inneren Schleife werden die Elemente der Positionen <code>i<\/code> (Anfang des rechten Teils) und <code>minPos<\/code> ausgetauscht (es sei denn, es handelt sich um dasselbe Element).<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">SelectionSort<\/span> <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">sort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> length = elements.length;\n\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; length - <span class=\"hljs-number\">1<\/span>; i++) {\n      <span class=\"hljs-comment\">\/\/ Search the smallest element in the remaining array<\/span>\n      <span class=\"hljs-keyword\">int<\/span> minPos = i;\n      <span class=\"hljs-keyword\">int<\/span> min = elements&#091;minPos];\n      <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> j = i + <span class=\"hljs-number\">1<\/span>; j &lt; length; j++) {\n        <span class=\"hljs-keyword\">if<\/span> (elements&#091;j] &lt; min) {\n          minPos = j;\n          min = elements&#091;minPos];\n        }\n      }\n\n      <span class=\"hljs-comment\">\/\/ Swap min with element at pos i<\/span>\n      <span class=\"hljs-keyword\">if<\/span> (minPos != i) {\n        elements&#091;minPos] = elements&#091;i];\n        elements&#091;i] = min;\n      }\n    }\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Der abgebildete Code unterscheidet sich insofern von der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/SelectionSort.java\" target=\"_blank\">SelectionSort im GitHub-Repository<\/a>, als dass diese das <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/SortAlgorithm.java\" target=\"_blank\">Interface SortAlgorithm<\/a> implementiert, um innerhalb des Testframeworks einfach austauschbar zu sein.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"selection-sort-zeitkomplexitaet\">Selection Sort Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p>Wir bezeichnen die Anzahl der Elemente mit <em>n<\/em>, in unserem Beispiel ist <em>n = 6<\/em>.<\/p>\n\n\n\n<p>Die zwei ineinander verschachtelten Schleifen sind ein Indiz daf\u00fcr, dass wir es mit einer Zeitkomplexit\u00e4t* von <em>O(n\u00b2)<\/em> zu tun haben. Das w\u00e4re dann der Fall, wenn beide Schleifen bis zu einem Wert iterieren, der linear mit <em>n<\/em> steigt.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<p>Bei der \u00e4u\u00dferen Schleife ist das offensichtlich der Fall: diese z\u00e4hlt bis <em>n-1<\/em>.<\/p>\n\n\n\n<p>Wie sieht es mit der inneren Schleife aus?<\/p>\n\n\n\n<p>Dies soll die folgende Grafik zeigen:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1100\" height=\"1212\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet.png\" alt=\"Selection Sort Zeitkomplexit\u00e4t\" class=\"wp-image-14283\" style=\"width:550px;height:606px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet.png 1100w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-224x247.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-336x370.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-504x555.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-672x740.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-400x441.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-600x661.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-800x881.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_zeitkomplexitaet-944x1040.png 944w\" sizes=\"(max-width: 1100px) 100vw, 1100px\" \/><\/figure>\n<\/div>\n\n\n<p>In jedem Schritt wird jeweils ein Vergleich weniger ausgef\u00fchrt als es unsortierte Elemente gibt. In Summe sind es 15 Vergleiche \u2013 und zwar unabh\u00e4ngig davon, ob das Array vorab sortiert ist oder nicht.<\/p>\n\n\n\n<p>Das l\u00e4sst sich auch wie folgt berechnen:<\/p>\n\n\n\n<p>Sechs Elemente mal f\u00fcnf Schritte; geteilt durch zwei, da im Durchschnitt \u00fcber alle Schritte die H\u00e4lfte der Elemente noch unsortiert ist:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>6 \u00d7 5 \u00d7 \u00bd &nbsp; = &nbsp; 30 \u00d7 \u00bd &nbsp; = &nbsp; 15<\/em><\/p>\n\n\n\n<p>Ersetzen wir <em>6<\/em> durch <em>n<\/em>, erhalten wir:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em>n \u00d7 (n \u2013 1) \u00d7 <em>\u00bd<\/em><\/em><\/p>\n\n\n\n<p>Ausmultipliziert ergibt das:<\/p>\n\n\n\n<p class=\"has-text-align-center\"><em><em><em>\u00bd<\/em><\/em> n\u00b2 \u2013 <em><em>\u00bd<\/em><\/em> n<\/em><\/p>\n\n\n\n<p>Die h\u00f6chste Potenz von <em>n<\/em> in diesem Term ist <em>n\u00b2<\/em>. Die Zeitkomplexit\u00e4t f\u00fcr das Suchen des kleinsten Elements betr\u00e4gt somit <em>O(n\u00b2)<\/em> \u2013 auch \u201equadratischer Aufwand\u201c genannt.<\/p>\n\n\n\n<p>Betrachten wir nun das Vertauschen der Elemente: In jedem Schritt (bis auf den letzten) wird entweder <em>ein<\/em> Element vertauscht oder <em>keines<\/em>, je nachdem, ob sich das jeweils kleinste Element bereits an der richtigen Position befindet oder nicht. Damit haben wir in Summe maximal <em>n-1<\/em> Tauschopertionen, also eine Zeitkomplexit\u00e4t von <em>O(n)<\/em> \u2013 auch \"linearer Aufwand\" genannt.<\/p>\n\n\n\n<p>F\u00fcr die Gesamtkomplexit\u00e4t z\u00e4hlt nur die h\u00f6chste Komplexit\u00e4tsklasse, daher gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Selection Sort betr\u00e4gt im&nbsp;<em>average<\/em>, <em>best<\/em> und <em>worst&nbsp;case<\/em>:&nbsp;<em>O(n\u00b2)<\/em><\/p>\n\n\n\n<p class=\"hc-footnote\">* Die Begriffe \u201eZeitkomplexit\u00e4t\u201c und \u201eO-Notation\u201c werden&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">in diesem Artikel<\/a>&nbsp;anhand von Beispielen und Diagrammen erkl\u00e4rt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-des-java-selection-sort-beispiels\">Laufzeit des Java Selection Sort-Beispiels<\/h3>\n\n\n\n<p>Genug der Theorie! Ich habe ein <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/UltimateTest.java\" target=\"_blank\">Testprogramm<\/a> geschrieben, das die Laufzeit von Selection Sort (und aller anderen in dieser Serie behandelten Sortieralgorithmen) wie folgt misst:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Die Anzahl der zu sortierenden Elemente verdoppelt sich nach jeder Iteration von anf\u00e4nglich 1.024 Elementen auf 536.870.912 (= 2<sup>29<\/sup>) Elemente. Ein doppelt so gro\u00dfes Array l\u00e4sst sich in Java nicht erstellen.<\/li>\n\n\n\n<li>Wenn ein Test l\u00e4nger als 20 Sekunden dauert, wird das Array nicht weiter vergr\u00f6\u00dfert.<\/li>\n\n\n\n<li>Alle Tests werden mit unsortierten, sowie aufsteigend und absteigend vorsortierten Elementen durchgef\u00fchrt.<\/li>\n\n\n\n<li>Dem HotSpot-Compiler wird zwei WarmUp-Runden Zeit gelassen den Code zu optimieren, danach werden die Tests so lange wiederholt, bis der Prozess abgebrochen wird. <\/li>\n<\/ul>\n\n\n\n<p>Nach jeder Wiederholung gibt das Programm den Median aller bisherigen Messergebnisse aus.<\/p>\n\n\n\n<p>Hier ist das Ergebnis f\u00fcr Selection Sort nach 50 Wiederholungen (dies ist der \u00dcbersicht halber nur ein Auszug; das vollst\u00e4ndige Ergebnis&nbsp;<a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-05-30\/Test_Results_Selection_Sort.txt\" target=\"_blank\" rel=\"noopener\">findest du hier<\/a>):<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">aufsteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.384<\/td><td class=\"has-text-align-right\" data-align=\"right\">27,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">26,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">65,6 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">32.768<\/td><td class=\"has-text-align-right\" data-align=\"right\">108,0 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">105,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">265,4 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">65.536<\/td><td class=\"has-text-align-right\" data-align=\"right\">434,0 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">424,3 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.052,2 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">131.072<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.729,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.714,1 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.209,9 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">262.144<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.913,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.880,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">16.863,7 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">524.288<\/td><td class=\"has-text-align-right\" data-align=\"right\">27.649,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">27.568,7 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">67.537,8 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Hier die Messwerte noch einmal als Diagramm (wobei ich \"unsortiert\" und \"aufsteigend\" aufgrund der fast identischen Werte als eine Kurve dargestellt habe):<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1504\" height=\"872\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime.png\" alt=\"Selection Sort Laufzeit im average, worst und best case\" class=\"wp-image-14153\" style=\"width:752px;height:436px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime.png 1504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-224x130.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-336x195.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-504x292.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-672x390.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-400x232.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-600x348.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-800x464.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-944x547.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_runtime-1200x696.png 1200w\" sizes=\"(max-width: 1504px) 100vw, 1504px\" \/><\/figure>\n<\/div>\n\n\n<p>Es l\u00e4sst sich sehr gut erkennen,<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>dass sich die Laufzeit bei Verdoppelung der Anzahl der Elemente in etwa vervierfacht \u2013 und zwar unabh\u00e4ngig davon, ob die Elemente vorsortiert sind oder nicht. Dies entspricht der erwarteten Zeitkomplexit\u00e4t <em>O(n\u00b2)<\/em>.<\/li>\n\n\n\n<li>dass die Laufzeit bei aufsteigend sortierten Elementen minimal besser ist als bei unsortierten Elementen. Dies liegt daran, dass hier die Tauschoperationen wegfallen, welche \u2013 wie zuvor analysiert \u2013 kaum ins Gewicht fallen.<\/li>\n\n\n\n<li>dass die Laufzeit bei absteigend sortierten Elementen deutlich schlechter ist als bei unsortierten Elementen.<\/li>\n<\/ul>\n\n\n\n<p>Wieso ist das so?<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"analyse-der-worst-case-laufzeit\">Analyse der worst case-Laufzeit<\/h3>\n\n\n\n<p>Das Suchen des jeweils kleinsten Elements sollte doch theoretisch \u2013 unabh\u00e4ngig von der Ausgangslage \u2013 immer gleich lang dauern; und die Tauschoperationen sollten bei absteigend sortierten Elementen nur minimal mehr sein (bei absteigend sortierten Elementen m\u00fcsste <em>jedes<\/em> getauscht werden; bei unsortierten gesch\u00e4tzt <em>fast jedes<\/em>).<\/p>\n\n\n\n<p>Mit dem Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/CountOperations.java\" target=\"_blank\">CountOperations<\/a> aus meinem GitHub-Repository k\u00f6nnen wir uns die Anzahl der verschiedenen Operationen anzeigen lassen. Hier die Ergebnisse f\u00fcr unsortierte und absteigend sortierte Elemente in einer Tabelle zusammengefasst:<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">Vergleiche<\/th><th class=\"has-text-align-right\" data-align=\"right\">Tauschen<br>unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">Tauschen<br>absteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">minPos\/min<br>unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\">minPos\/min<br>absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">512<\/td><td class=\"has-text-align-right\" data-align=\"right\">130.816<\/td><td class=\"has-text-align-right\" data-align=\"right\">504<\/td><td class=\"has-text-align-right\" data-align=\"right\">256<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.866<\/td><td class=\"has-text-align-right\" data-align=\"right\">66.047<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">523.776<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.017<\/td><td class=\"has-text-align-right\" data-align=\"right\">512<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.439<\/td><td class=\"has-text-align-right\" data-align=\"right\">263.167<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">2.048<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.096.128<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.042<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">14.727<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.050.623<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.096<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.386.560<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.084<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.048<\/td><td class=\"has-text-align-right\" data-align=\"right\">30.758<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.198.399<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">8.192<\/td><td class=\"has-text-align-right\" data-align=\"right\">33.550.336<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.181<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.096<\/td><td class=\"has-text-align-right\" data-align=\"right\">69.378<\/td><td class=\"has-text-align-right\" data-align=\"right\">16.785.407<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Aus den Messwerten l\u00e4sst sich erkennen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Bei absteigend sortierten Elementen haben wir \u2013 wie erwartet \u2013 genauso viele Vergleichsoperationen wie bei unsortierten Elementen \u2013 n\u00e4mlich <em>n \u00d7 (n-1) \/ 2<\/em>.<\/li>\n\n\n\n<li>Bei unsortierten Elementen haben wir \u2013 wie vermutet \u2013 beinahe so viele Tauschoperationen wie Elemente: bei 4.096 unsortierten Elementen sind es beispielsweise 4.084 Tauschoperationen. Diese Zahlen \u00e4ndern sich zufallsbedingt leicht von Test zu Test.<\/li>\n\n\n\n<li>Bei absteigend sortierten Elementen haben wir allerdings nur halb so viele Tauschoperationen wie Elemente! Dies liegt daran, dass wir beim Vertauschen nicht nur jeweils das kleinste Element an die richtige Stelle setzen, sondern auch den jeweiligen Tauschpartner.<\/li>\n<\/ul>\n\n\n\n<p>Bei acht Elementen haben wir beispielsweise vier Tauschoperationen. In den ersten vier Iterationen jeweils eine und in den Iterationen f\u00fcnf bis acht keine mehr (dennoch l\u00e4uft der Algorithmus bis zum Ende weiter):<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1292\" height=\"1406\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2.png\" alt=\"Selection Sort Tauschoperationen bei absteigend sortierten Elementen\" class=\"wp-image-14184\" style=\"width:646px;height:703px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2.png 1292w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-224x244.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-336x366.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-504x548.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-672x731.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-400x435.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-600x653.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-800x871.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-944x1027.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_descending_swaps-v2-1200x1306.png 1200w\" sizes=\"(max-width: 1292px) 100vw, 1292px\" \/><\/figure>\n<\/div>\n\n\n<p>Des weiteren l\u00e4sst sich an den Messwerten ablesen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Den Grund, warum Selection Sort bei absteigend sortierten Elementen so deutlich langsamer ist, finden wir in der Anzahl der lokalen Variablenzuweisungen (<code>minPos<\/code> und <code>min<\/code>) bei der Suche nach dem kleinsten Element: W\u00e4hrend wir bei 8.192 <em>unsortierten<\/em> Elementen 69.378 dieser Zuweisungen haben, sind es bei <em>absteigend sortierten<\/em> Elementen 16.785.407 Zuweisungen \u2013 das sind 242 mal so viele!<\/li>\n<\/ul>\n\n\n\n<p>Warum dieser massive Unterschied?<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Analyse der Laufzeit der Suche nach dem kleinsten Element<\/h4>\n\n\n\n<p>F\u00fcr absteigend sortierte Elemente l\u00e4sst sich die Gr\u00f6\u00dfenordnung an der Grafik von soeben herleiten: Die Suche nach dem kleinsten Element beschr\u00e4nkt sich auf das Dreieck aus den orangenen und orange-blauen K\u00e4stchen. Im oberen, orangenen Teil werden die Zahlen in jedem Feld kleiner, im rechten orange-blauen Teil steigen die Zahlen wieder an. <\/p>\n\n\n\n<p>Zuweisungsoperationen finden in jedem orangenen K\u00e4stchen statt sowie im jeweils ersten der orange-blauen. Die Anzahl der Zuweisungsoperationen f\u00fcr <code>minPos<\/code> und <code>min<\/code> ist also bildlich gesprochen in etwa \"ein Viertel des Quadrats\" \u2013 mathematisch und ganz exakt sind es: <em>\u00bc n\u00b2 + n - 1<\/em>.<\/p>\n\n\n\n<p>F\u00fcr unsortierte Elemente m\u00fcssten wir deutlich tiefer in die Materie eindringen. Dies w\u00fcrde nicht nur den Rahmen dieses Artikels, sondern des gesamten Blogs, sprengen. <\/p>\n\n\n\n<p>Ich beschr\u00e4nke meine Analyse daher auf ein kleines <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/FindMinimumTest.java\" target=\"_blank\">Demo-Programm<\/a>, welches misst, wie viele <code>minPos<\/code>\/<code>min<\/code>-Zuweisungen es bei der Suche nach dem kleinsten Element in einem unsortierten Array gibt. Hier die durchschnittlichen Werte nach 100 Iterationen (ein kleiner Auszug; die kompletten Ergebnisse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-06-23\/FindMinimumTest.log\" target=\"_blank\">findest Du hier<\/a>):<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes more-h-padding\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">durchschnittliche Anzahl<br>minPos\/min-Zuweisungen<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">7.08<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.096<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.61<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.385<\/td><td class=\"has-text-align-right\" data-align=\"right\">8.94<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">65.536<\/td><td class=\"has-text-align-right\" data-align=\"right\">11.81<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">262.144<\/td><td class=\"has-text-align-right\" data-align=\"right\">12.22<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">1.048.576<\/td><td class=\"has-text-align-right\" data-align=\"right\">14.26<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.194.304<\/td><td class=\"has-text-align-right\" data-align=\"right\">14.71<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.777.216<\/td><td class=\"has-text-align-right\" data-align=\"right\">16.44<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">67.108.864<\/td><td class=\"has-text-align-right\" data-align=\"right\">17.92<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">268.435.456<\/td><td class=\"has-text-align-right\" data-align=\"right\">20.27<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Hier das ganze als Diagramm mit logarithmischer x-Achse:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1484\" height=\"804\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments.png\" alt=\"Number of minPos\/min assignments in relation to the number of elements\" class=\"wp-image-14150\" style=\"width:742px;height:402px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments.png 1484w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-224x121.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-336x182.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-504x273.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-672x364.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-400x217.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-600x325.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-800x433.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-944x511.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/searching_smallest_element_avg_assignments-1200x650.png 1200w\" sizes=\"(max-width: 1484px) 100vw, 1484px\" \/><\/figure>\n<\/div>\n\n\n<p>Am Diagramm sieht man sehr sch\u00f6n, dass wir hier ein logarithisches Wachstum haben, d. h. mit jeder Verdoppelung der Anzahl der Elemente erh\u00f6ht sich die Anzahl der Zuweisungen nur um einen konstanten Wert. Auf die mathematischen Hintergr\u00fcnde gehe ich, wie gesagt, hier nicht weiter ein.<\/p>\n\n\n\n<p>Dies ist der Grund, warum diese <code>minPos<\/code>\/<code>min<\/code>-Zuweisungen bei unsortierten Arrays kaum ins Gewicht fallen.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"weitere-eigenschaften-von-selection-sort\">Weitere Eigenschaften von Selection Sort<\/h2>\n\n\n\n<p>Im folgenden werden die Platzkomplexit\u00e4t, Stabilit\u00e4t und Parallelisierbarkeit von Selection Sort behandelt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"platzkomplexitaet-von-selection-sort\">Platzkomplexit\u00e4t von Selection Sort<\/h3>\n\n\n\n<p>Die Platzkomplexit\u00e4t von Selection Sort ist konstant, da wir au\u00dfer den Schleifenvariablen <code>i<\/code> und <code>j<\/code>, sowie den Hilfsvariablen <code>length<\/code>, <code>minPos<\/code> und <code>min<\/code> keinen zus\u00e4tzlichen Speicherplatz ben\u00f6tigen. <\/p>\n\n\n\n<p>D. h. egal wie viele Elemente wir sortieren \u2013 zehn oder zehn Millionen \u2013 wir ben\u00f6tigen immer nur diese f\u00fcnf zus\u00e4tzlichen Variablen. Konstanten Aufwand notiert man als&nbsp;<em>O(1)<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stabilitaet-von-selection-sort\">Stabilit\u00e4t von Selection Sort<\/h3>\n\n\n\n<p>Selection Sort erscheint auf den ersten Blick stabil: Wenn im unsortierten Teil mehrere Elemente mit dem gleichen Key vorkommen, sollte das erste davon doch auch als erstes an den sortierten Teil angeh\u00e4ngt werden.<\/p>\n\n\n\n<p>Doch der Schein tr\u00fcgt. Denn durch das Tauschen zweier Elemente im zweiten Teilschritt des Algorithmus kann es passieren, dass bestimmte Elemente im unsortierten Teil nicht mehr die urspr\u00fcngliche Reihenfolge haben. Dies f\u00fchrt dann wiederum dazu, dass sie letztlich auch im sortierten Teil nicht mehr in der urspr\u00fcnglichen Reihenfolge erscheinen. <\/p>\n\n\n\n<p>Ein Beispiel kann sehr einfach konstruiert werden. Angenommen wir haben zwei unterschiedliche Elemente mit dem Key 2 und eines mit dem Key 1, die wie folgt angeordnet sind, und sortieren diese mit Selection Sort:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1188\" height=\"846\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil.png\" alt=\"Selection Sort nicht stabil\" class=\"wp-image-14285\" style=\"width:594px;height:423px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil.png 1188w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-224x160.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-336x239.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-504x359.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-672x479.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-400x285.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-600x427.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-800x570.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_nicht_stabil-944x672.png 944w\" sizes=\"(max-width: 1188px) 100vw, 1188px\" \/><\/figure>\n<\/div>\n\n\n<p>Im ersten Schritt werden das erste und letzte Element vertauscht. Damit landet das Element \"TWO\" hinter dem Element \"two\" \u2013 die Reihenfolge beider Elemente ist vertauscht.<\/p>\n\n\n\n<p>Im zweiten Schritt vergleicht der Algorithmus die beiden hinteren Elemente. Beide haben den gleichen Key, 2. Es wird also kein Element vertauscht.<\/p>\n\n\n\n<p>Im dritten Schritt verbleibt nur ein Element, dieses gilt automatisch als sortiert.<\/p>\n\n\n\n<p>Die zwei Elemente mit dem Key 2 sind also gegen\u00fcber ihrer Ausgangsreihenfolge vertauscht worden \u2013 der Algorithmus ist unstabil.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Stabile Variante von Selection Sort<\/h4>\n\n\n\n<p>Selection Sort kann stabil gemacht werden, indem in Schritt zwei das kleinste Element nicht mit dem ersten vertauscht wird, sondern zwischen dem ersten und dem kleinsten Elemente alle Elemente um eine Position nach rechts geschoben werden und das kleinste Element an den Anfang gesetzt wird.<\/p>\n\n\n\n<p>Auch wenn die Zeitkomplexit\u00e4t durch diese \u00c4nderung gleichbleiben wird, f\u00fchren die zus\u00e4tzlichen Verschiebungen zu einer deutlichen Verschlechterung der Performance, zumindest wenn wir ein Array sortieren.<\/p>\n\n\n\n<p>Bei einer verketteten Liste k\u00f6nnte das Ausschneiden und Einf\u00fcgen des einzusortierenden Elements ohne signifikanten Performanceverlust durchgef\u00fchrt werden. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"parallelisierbarkeit-von-selection-sort\">Parallelisierbarkeit von Selection Sort<\/h3>\n\n\n\n<p>Die \u00e4u\u00dfere Schleife ist nicht parallelisierbar, da diese den Inhalt des Arrays in jedem Schritt \u00e4ndert. <\/p>\n\n\n\n<p>Die innere Schleife (Suche nach dem kleinsten Element) kann parallelisiert werden, in dem das Array aufgeteilt wird, in jedem Teilarray parallel das kleinste Element gesucht wird, und dann die Zwischenergebnisse zusammengef\u00fchrt werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"selection-sort-vs-insertion-sort\">Selection Sort vs. Insertion Sort<\/h2>\n\n\n\n<p>Welcher Algorithmus ist schneller, Selection Sort oder <a href=\"\/de\/algorithmen\/insertion-sort\/\">Insertion Sort<\/a>?<\/p>\n\n\n\n<p>Im folgenden stelle ich die Messwerte aus meinen Java-Implementierungen gegen\u00fcber. Den <em>best case<\/em> lasse ich au\u00dfen vor; dieser hat bei Insertion Sort eine Zeitkomplexit\u00e4t von <em>O(n)<\/em> und hat bis zu 524.288 Elementen weniger als eine Millisekunde gebraucht \u2013 ist also in jedem Fall um Gr\u00f6\u00dfenordnungen schneller als Selection Sort.<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th class=\"has-text-align-right\" data-align=\"right\">n<\/th><th class=\"has-text-align-right\" data-align=\"right\">Selection Sort<br>unsortiert<\/th><th class=\"has-text-align-right\" data-align=\"right\"><strong>Insertion Sort<\/strong><br><strong>unsortiert<\/strong><\/th><th class=\"has-text-align-right\" data-align=\"right\">Selection Sort<br>absteigend<\/th><th class=\"has-text-align-right\" data-align=\"right\">Insertion Sort<br>absteigend<\/th><\/tr><\/thead><tbody><tr><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><td class=\"has-text-align-right\" data-align=\"right\">...<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.384<\/td><td class=\"has-text-align-right\" data-align=\"right\">27,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">21,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">65,6 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">43,6 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">32.768<\/td><td class=\"has-text-align-right\" data-align=\"right\">108,0 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">87,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">265,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">175,8 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">65.536<\/td><td class=\"has-text-align-right\" data-align=\"right\">434,0 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">350,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.052,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">697,6 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">131.072<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.729,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.398,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.209,9 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.840,0 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">262.144<\/td><td class=\"has-text-align-right\" data-align=\"right\">6.913,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">5.706,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">16.863,7 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">11.517,4 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">524.288<\/td><td class=\"has-text-align-right\" data-align=\"right\">27.649,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">23.009,7 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">67.537,8 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">46.309,3 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Und noch einmal als Diagramm:<\/p>\n\n\n<div class=\"wp-block-image hc-img-border-grey\">\n<figure class=\"aligncenter size-full is-resized\"><img decoding=\"async\" width=\"1504\" height=\"872\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime.png\" alt=\"Laufzeit von Selection Sort und Insertion Sort\" class=\"wp-image-14204\" style=\"width:752px;height:436px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime.png 1504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-224x130.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-336x195.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-504x292.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-672x390.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-400x232.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-600x348.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-800x464.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-944x547.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection_sort_vs_insertion_sort_runtime-1200x696.png 1200w\" sizes=\"(max-width: 1504px) 100vw, 1504px\" \/><\/figure>\n<\/div>\n\n\n<p>Insertion Sort ist also nicht nur im <em>best case<\/em>, sondern auch im <em>average<\/em> und <em>worst case<\/em> schneller als Selection Sort.<\/p>\n\n\n\n<p>Der Grund daf\u00fcr ist, dass Insertion Sort mit durchschnittlich halb so vielen Vergleichen auskommt. Zur Erinnerung: bei Insertion Sort haben wir Vergleiche und Verschiebungen bis durchschnittlich zur <em>H\u00e4lfte<\/em> der sortierten Elemente; bei Selection Sort m\u00fcssen wir in jedem Schritt in <em>allen<\/em> unsortierten Elementen das kleinste Element suchen.<\/p>\n\n\n\n<p>Bei Selection Sort haben wir deutlich weniger Schreiboperationen, so dass Selection Sort schneller sein kann, wenn Schreiboperationen teuer sind. Beim sequentiellen Schreiben in Arrays ist das nicht der Fall, da dies gr\u00f6\u00dftenteils im CPU-Cache erfolgt.<\/p>\n\n\n\n<p>In der Praxis wird daher so gut wie ausschlie\u00dflich Insertion Sort angewendet.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusamenfassung\">Zusamenfassung<\/h2>\n\n\n\n<p>Selection Sort ist ein einfach zu implementierender, in der Standardimplementierung nicht stabiler Sortiergorithmus mit einer Zeitkomplexit\u00e4t von <em>O(n\u00b2)<\/em> im <em>average<\/em>, <em>best<\/em> und <em>worst case<\/em>.<\/p>\n\n\n\n<p>Selection Sort ist langsamer als Insertion Sort, weshalb es in der Praxis nicht angewendet wird.<\/p>\n\n\n\n<p>Weitere Sortieralgorithmen findest du in dieser&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/sortieralgorithmen\/#Vergleich_der_wichtigsten_Sortieralgorithmen\">\u00dcbersicht aller Sortieralgorithmen und ihrer Eigenschaften<\/a>&nbsp;im ersten Teil der Artikelserie.<\/p>\n\n\n\n<p><\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel beschreibe ich, wie Selection Sort funktioniert, zeige den Java-Quellcode und erkl\u00e4re die Herleitung der Zeitkomplexit\u00e4t.<\/p>\n","protected":false},"author":1,"featured_media":43243,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"video","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Wie funktioniert Selection Sort? Mit Illustrationen und Quellcode. Wie bestimmt man seine Zeitkomplexit\u00e4t (ohne komplizierte Mathematik)?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":17768,"_post_count":0,"footnotes":""},"categories":[127],"tags":[129],"class_list":["post-12209","post","type-post","status-publish","format-video","has-post-thumbnail","hentry","category-algorithmen","tag-sortieralgorithmen","post_format-post-format-video"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/06\/selection-sort-java-feature-image.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"In diesem Artikel beschreibe ich, wie Selection Sort funktioniert, zeige den Java-Quellcode und erkl\u00e4re die Herleitung der Zeitkomplexit\u00e4t.","public_identification_id":"8c93ed65f7a34d6f9a4411e300fab0e2","private_identification_id":"a67b2b90fa04484d9c3681bb386e9834","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12209","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=12209"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12209\/revisions"}],"predecessor-version":[{"id":52512,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12209\/revisions\/52512"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43243"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12209"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12209"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}