{"id":12213,"date":"2020-07-22T09:00:00","date_gmt":"2020-07-22T07:00:00","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=12213"},"modified":"2025-06-12T09:23:49","modified_gmt":"2025-06-12T07:23:49","slug":"quicksort","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/quicksort\/","title":{"rendered":"Quicksort \u2013 Algorithmus, Quellcode, Zeitkomplexit\u00e4t"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">In der <a href=\"\/de\/algorithmen\/sortieralgorithmen\/\">Artikelserie \u00fcber Sortieralgorithmen<\/a> kommem wir nach drei relativ leicht zu verstehenden Sortierverfahren (<a href=\"\/de\/algorithmen\/insertion-sort\/\">Insertion Sort<\/a>, <a href=\"\/de\/algorithmen\/selection-sort\/\">Selection Sort<\/a>, <a href=\"\/de\/algorithmen\/bubble-sort\/\">Bubble Sort<\/a>) zu den komplexeren \u2013 daf\u00fcr aber auch deutlich effizienteren Algorithmen. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir beginnen mit Quicksort (\"Sort\" ist hier kein separates Wort, also nicht \"Quick Sort\"). Dieser Artikel:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>beschreibt den Quicksort-Algorithmus,<\/li>\n\n\n\n<li>zeigt dessen Quellcode in Java,<\/li>\n\n\n\n<li>erkl\u00e4rt, wie man die Zeitkomplexit\u00e4t von Quicksort herleitet,<\/li>\n\n\n\n<li>testet, ob die Performance der Java-Implementierung mit dem erwarteten Laufzeitverhalten \u00fcbereinstimmt,<\/li>\n\n\n\n<li>stellt mehrere Algorithmus-Optimierungen vor (Kombination mit Insertion Sort und Dual-Pivot Quicksort)<\/li>\n\n\n\n<li>und misst und vergleicht auch deren Geschwindigkeit.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die Quellcodes der 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=\"Quicksort Algorithmus [mit Animation, Deutsch]\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/ka24mbzv93w?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=\"quicksort-algorithmus\">Quicksort Algorithmus<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Quicksort funktioniert nach dem \"Teile-und-herrsche\"-Prinzip (\"divide and conquer\"):<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Als erstes teilen wir die zu sortierenden Elemente auf zwei Bereiche auf \u2013 einen mit kleinen Elementen (im folgenen Beispiel \"A\") und einen mit gro\u00dfen Elementen (im Beispiel \"B\"). <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Welche Elemente klein sind und welche gro\u00df, entscheidet dabei das sogenannte <em>Pivot-Element<\/em>. Das Pivot-Element kann ein beliebiges Element aus dem Eingabe-Array sein. (Welches man w\u00e4hlt, bestimmt die <em>Pivot-Strategie<\/em>, dazu sp\u00e4ter mehr.)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Das Array wird nun so umsortiert, dass <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>die Elemente, die kleiner als das Pivot-Element sind, im linken Bereich landen,<\/li>\n\n\n\n<li>die Elemente, die gr\u00f6\u00dfer als das Pivot-Element sind, im rechten Bereich landen,<\/li>\n\n\n\n<li>und dass das Pivot-Element zwischen den zwei Bereichen positioniert wird \u2013 und damit automatisch an seiner endg\u00fcltigen Position.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">In folgendem Beispiel werden die Elemente [3, 7, 1, 8, 2, 5, 9, 4, 6] auf diese Art umsortiert. Als Pivot-Element habe ich das letzte Element des unsortierten Eingabe-Arrays gew\u00e4hlt (die orange gef\u00e4rbte 6):<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7.png\" alt=\"Quicksort-Algorithmus - Schritt 1\" class=\"wp-image-12245\" style=\"width:760px;height:420px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step1_v7-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Dieses Aufteilen auf zwei Teil-Arrays nennt man <em>Partitionieren<\/em>. Wie die Partitionierung genau funktioniert, erf\u00e4hrst du im n\u00e4chsten Abschnitt. Vorher zeige ich dir, wie der \u00fcbergeordnete Algorithmus weitergeht.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Teil-Arrays links und rechts des Pivot-Elements sind nach der Partitionierung weiterhin unsortiert. Die Teil-Arrays werden nun ebenfalls partitioniert. Das Pivot-Element aus dem vorherigen Schritt, die 6, habe ich halbtransparent dargestellt, um die zwei Teil-Arrays besser erkennen zu k\u00f6nnen:<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5.png\" alt=\"Quicksort-Algorithmus - Schritt 2\" class=\"wp-image-12249\" style=\"width:760px;height:420px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step2_v5-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Nach der erneuten Partitionierung haben wir vier Bereiche: Aus A sind A1 und A2 entstanden; aus B sind B1 und B2 hervorgegangen. Die Bereiche A1, B1 und B2 bestehen aus nur noch einem Element und gelten damit als sortiert (\"beherrscht\" im Sinne von \"Teile und herrsche\"). Jetzt m\u00fcssen wir nur noch das Teil-Array A2 partitionieren:<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5.png\" alt=\"Quicksort-Algorithmus - Schritt 3\" class=\"wp-image-12251\" style=\"width:760px;height:420px\" title=\"\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_step3_v5-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die zwei in diesem Schritt aus A2 entstandenen Partitionen A2a und A2b haben wieder die L\u00e4nge 1 und gelten damit als sortiert. Somit sind alle Teil-Arrays sortiert \u2013 und damit auch das gesamte Array:<\/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=\"1520\" height=\"732\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3.png\" alt=\"Quicksort-Algorithmus - Beendet\" class=\"wp-image-14724\" style=\"width:760px;height:366px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-224x108.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-336x162.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-504x243.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-672x324.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-400x193.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-600x289.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-800x385.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-944x455.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_algorithm_step4_v3-1200x578.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Der Algorithmus ist damit beendet.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wie die Aufteilung eines Arrays in zwei Bereiche funktioniert \u2013 die Partitionierung \u2013 erkl\u00e4re ich im n\u00e4chsten Abschnitt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-partitionierung\">Quicksort Partitionierung<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die Aufteilung des Arrays in zwei Partitionen erfolgt, in dem wir von links beginnend nach Elementen suchen, die gr\u00f6\u00dfer als das Pivot-Element sind, und von rechts beginnend nach Elementen, die kleiner sind als das Pivot-Element.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Diese Elemente werden dann jeweils vertauscht. Dies wiederholen wir solange, bis die linke und rechte Suchposition aufeinander getroffen oder aneinander vorbeigelaufen sind.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im Beispiel von oben funktioniert das wie folgt:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Das erste Element von links, das gr\u00f6\u00dfer als das Pivot-Element 6 ist, ist die 7.<\/li>\n\n\n\n<li>Das erste Element von rechts, das kleiner als die 6 ist, ist die 4. <\/li>\n\n\n\n<li>Wir vertauschen die 7 und die 4.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Die 3 befand sich bereits auf der richtigen Seite (kleiner als 6, also links). Ich habe sie schw\u00e4cher eingef\u00e4rbt, da wir sie nicht weiter betrachten m\u00fcssen.<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4.png\" alt=\"Quicksort-Partitionierung - Schritt 1\" class=\"wp-image-12256\" style=\"width:760px;height:420px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step1_v4-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Wir suchen weiter und finden von links aus die 8 (die 1 ist schon auf der richtigen Seite, da kleiner als 6) und von rechts aus die 5 (die 9 ist ebenfalls bereits auf der richtigen Seite, da gr\u00f6\u00dfer als 6). Wir vertauschen die 8 und die 5:<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6.png\" alt=\"Quicksort-Partitionierung - Schritt 2\" class=\"wp-image-12257\" style=\"width:760px;height:420px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step2_v6-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Nun treffen sich die linke und rechte Suchposition an der 2. Das Vertauschen endet hier. Da die 2 kleiner ist als das Pivot-Element, schieben wir den Suchzeiger noch eine Position nach rechts, auf die 8, so dass alle Elemente ab dieser Position gr\u00f6\u00dfer oder gleich dem Pivot-Element sind und alle Elemente davor kleiner:<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6.png\" alt=\"Quicksort-Partitionierung - Schritt 3\" class=\"wp-image-12262\" style=\"width:760px;height:420px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step3_v6-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Damit das Pivot-Element am <em>Anfang<\/em> der rechten Partition steht, vertauschen wir noch die 8 mit der 6:<\/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=\"1520\" height=\"804\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3.png\" alt=\"Quicksort-Partitionierung - Schritt 3\" class=\"wp-image-12258\" style=\"width:760px;height:402px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-224x118.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-336x178.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-504x267.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-672x355.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-400x212.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-600x317.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-800x423.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-944x499.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step4_v3-1200x635.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die Partitionierung ist abgeschlossen: Die 6 befindet sich an der richtigen Position, die Zahlen links von der 6 sind kleiner und die Zahlen rechts davon gr\u00f6\u00dfer. Wir haben also den Stand erreicht, der im vorangegangenen Abschnitt nach der ersten Partitionierung gezeigt wurde:<\/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=\"1520\" height=\"840\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3.png\" alt=\"Quicksort-Partitionierung - Beendet\" class=\"wp-image-12264\" style=\"width:760px;height:420px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-224x124.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-336x186.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-504x279.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-672x371.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-400x221.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-600x332.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-800x442.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-944x522.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/05\/Quicksort_algorithm_partitioning_step5_v3-1200x663.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"das-pivot-element\">Das Pivot-Element<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\"Pivot\" ist franz\u00f6sisch und bedeutet \"Dreh- und Angelpunkt\".<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im vorangegangenen Beispiel habe ich jeweils das&nbsp;<em>letzte<\/em>&nbsp;Element eines (Teil-)Arrays als Pivot-Element ausgew\u00e4hlt. Diese Strategie hat den Vorteil, dass sie den Algorithmus besonders einfach macht; sie kann sich aber negativ auf die Performance auswirken. <\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Vorteil der Pivot-Strategie \"letztes Element\"<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Der Vorteil ist, wie oben erw\u00e4hnt, ein vereinfachter Algorithmus:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Da das Pivot-Element bei dieser Strategie garantiert im rechten Bereich liegt, brauchen wir es bei den Vergleichs- und Tauschoperationen nicht zu ber\u00fccksichtigen. Au\u00dferdem k\u00f6nnen wir im letzten Schritt der Partitionierung bedenkenlos das erste Element des rechten Bereichs mit dem Pivot-Element vertauschen, um dieses an seine finale Position zu setzen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Nachteil der Pivot-Strategie \"letztes Element\"<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In der Praxis f\u00fchrt die Strategie zu Problemen bei vorsortierten Eingabedaten. Bei einem aufsteigend sortierten Array w\u00e4re das Pivot-Element in jeder Iteration das gr\u00f6\u00dfte Element. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Damit w\u00fcrde das Array nicht mehr in zwei m\u00f6glichst gleich gro\u00dfe Partitionen aufgeteilt werden, sondern in eine leere (da kein Element gr\u00f6\u00dfer ist als das Pivotelement), und eine der L\u00e4nge <em>n-1<\/em> (mit allen Elementen au\u00dfer dem Pivot-Element). <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dies w\u00fcrde sich negativ auf die Performance auswirken (s. Abschnitt <a href=\"#Quicksort_Zeitkomplexitat\">\"Quicksort Zeitkomplexit\u00e4t\"<\/a>).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bei absteigend sortierte Eingabedaten w\u00e4re das Pivot-Element immer das <em>kleinste<\/em> Element, so dass die Partitionierung ebenfalls immer eine leere Partition und eine der Gr\u00f6\u00dfe <em>n-1<\/em> erzeugen w\u00fcrde.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"alternative-pivot-strategien\">Alternative Pivot-Strategien<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Alternative Strategien f\u00fcr die Auswahl des Pivot-Elements sind z. B.:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>das mittlere Element,<\/li>\n\n\n\n<li>ein zuf\u00e4lliges Element,<\/li>\n\n\n\n<li>der Median aus drei, f\u00fcnf oder mehr Elementen.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">W\u00e4hlt man auf eine dieser Arten das Pivot-Element aus, erh\u00f6ht sich die Wahrscheinlichkeit, dass die aus der Partitionierung hervorgehenden Teil-Arrays m\u00f6glichst gleich gro\u00df sind.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wie sich die Wahl der Pivot-Strategie auf die Performance auswirkt, werde ich im Laufe des Artikels erkl\u00e4ren.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Warum nicht der Median?<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Im optimalen Fall teilt das Pivot-Element das Array in zwei gleich gro\u00dfe H\u00e4lften. Warum w\u00e4hlt man dann nicht einfach den Median aller Elemente als Pivot-Element? <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Aus folgendem Grund: Um den Median zu bestimmen, m\u00fcsste man das Array erst einmal sortieren. Wir definieren aber gerade erst den Sortieralgorithmus \u2013 wir stehen also vor einem klassischen Henne-Ei-Problem.<\/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<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-java-quellcode\">Quicksort Java Quellcode<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Der folgende Java-Quellcode (Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/QuicksortSimple.java\" target=\"_blank\" rel=\"noopener\">QuicksortSimple<\/a> im GitHub-Repository) verwendet der Einfachheit halber als Pivot-Element immer das <em>rechte<\/em> Element eines zu sortierenden (Teil-)Arrays.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wie oben erl\u00e4utert, ist dies keine gute Wahl, wenn die Eingabedaten bereits sortiert sein k\u00f6nnten. Diese Variante macht den Code aber zun\u00e4chst einfacher zu verstehen.<\/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\">QuicksortSimple<\/span> <\/span>{\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/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    quicksort(elements, <span class=\"hljs-number\">0<\/span>, elements.length - <span class=\"hljs-number\">1<\/span>);\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">quicksort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right)<\/span> <\/span>{\n    <span class=\"hljs-comment\">\/\/ End of recursion reached?<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (left &gt;= right) {\n      <span class=\"hljs-keyword\">return<\/span>;\n    }\n\n    <span class=\"hljs-keyword\">int<\/span> pivotPos = partition(elements, left, right);\n    quicksort(elements, left, pivotPos - <span class=\"hljs-number\">1<\/span>);\n    quicksort(elements, pivotPos + <span class=\"hljs-number\">1<\/span>, right);\n  }\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">partition<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> pivot = elements&#091;right];\n\n    <span class=\"hljs-keyword\">int<\/span> i = left;\n    <span class=\"hljs-keyword\">int<\/span> j = right - <span class=\"hljs-number\">1<\/span>;\n    <span class=\"hljs-keyword\">while<\/span> (i &lt; j) {\n      <span class=\"hljs-comment\">\/\/ Find the first element &gt;= pivot<\/span>\n      <span class=\"hljs-keyword\">while<\/span> (elements&#091;i] &lt; pivot) {\n        i++;\n      }\n\n      <span class=\"hljs-comment\">\/\/ Find the last element &lt; pivot<\/span>\n      <span class=\"hljs-keyword\">while<\/span> (j &gt; left &amp;&amp; elements&#091;j] &gt;= pivot) {\n        j--;\n      }\n\n      <span class=\"hljs-comment\">\/\/ If the greater element is left of the lesser element, switch them<\/span>\n      <span class=\"hljs-keyword\">if<\/span> (i &lt; j) {\n        ArrayUtils.swap(elements, i, j);\n        i++;\n        j--;\n      }\n    }\n\n    <span class=\"hljs-comment\">\/\/ i == j means we haven't checked this index yet.<\/span>\n    <span class=\"hljs-comment\">\/\/ Move i right if necessary so that i marks the start of the right array.<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (i == j &amp;&amp; elements&#091;i] &lt; pivot) {\n      i++;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Move pivot element to its final position<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (elements&#091;i] != pivot) {\n      ArrayUtils.swap(elements, i, right);\n    }\n    <span class=\"hljs-keyword\">return<\/span> i;\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 class=\"wp-block-paragraph\">Erkl\u00e4rung des Quellcodes:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Methode <code>sort()<\/code> ruft <code>quicksort()<\/code> auf und \u00fcbergibt das Array sowie die Start- und Endpositionen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Methode <code>quicksort()<\/code> ruft zuerst die Methode <code>partition()<\/code> auf, um das Array zu partitionieren. Daraufhin ruft sie sich selbst rekursiv auf \u2013 einmal f\u00fcr das Teil-Array links des Pivot-Elements und einmal f\u00fcr das Teil-Array rechts des Pivot-Elements. Die Rekursion endet, wenn <code>quicksort()<\/code> f\u00fcr ein Sub-Array der L\u00e4nge 1 oder 0 aufgerufen wird.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Methode <code>partition()<\/code> partitioniert das Array und gibt die Position des Pivot-Elements zur\u00fcck. Die Variable <code>i<\/code> stellt den linken Suchzeiger dar, die Variabe <code>j<\/code> den rechten Suchzeiger. Die einzelnen Schritte der <code>partition()<\/code>-Methode sind im Code dokumentiert \u2013 sie entsprechen den Schritten des Beispiels aus dem Abschnitt <a href=\"#Quicksort_Partitionierung\">\"Quicksort Partitionierung\"<\/a>. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quellcode-fuer-alternative-pivot-strategien\">Quellcode f\u00fcr alternative Pivot-Strategien<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Wollen wir nicht das rechte, sondern ein anderes Element als Pivot-Element verwenden, muss der Algorithmus erweitert werden. Es gibt drei Varianten:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Algorithmus-Variante 1<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Die einfachste Variante ist es das gew\u00e4hlte Pivot-Element vorab mit dem rechten Element zu tauschen. In diesem Fall kann der restliche Quellcode unver\u00e4ndert bleiben.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Eine entsprechende Implementierung findest du in der Klasse <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/QuicksortVariant1.java\" target=\"_blank\" rel=\"noopener\">QuicksortVariant1<\/a> im GitHub-Repository. In dieser Variante wird vor jeder Partitionierung die Methode <code>findPivotAndMoveRight()<\/code> aufgerufen, die entsprechend der gew\u00e4hlten Strategie das Pivot-Element ausw\u00e4hlt und mit dem Element ganz rechts vertauscht.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">M\u00f6gliche Pivot-Strategien sind im Enum <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/PivotStrategy.java\">PivotStrategy<\/a> definiert und lauten:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>RANDOM<\/code>: ein zuf\u00e4lliges Element wird ausgew\u00e4hlt.<\/li>\n\n\n\n<li><code>LEFT<\/code>: das linke Element wird ausgew\u00e4hlt.<\/li>\n\n\n\n<li><code>RIGHT<\/code>: das rechte Element wird ausgew\u00e4hlt (entspricht letztendlich der oben abgedruckten Variante \"QuicksortSimple\").<\/li>\n\n\n\n<li><code>MIDDLE<\/code>: das mittlere Element wird ausgew\u00e4hlt.<\/li>\n\n\n\n<li><code>MEDIAN3<\/code>: der Median aus drei Elementen des Arrays wird als Pivot-Element ausgew\u00e4hlt.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Algorithmus-Variante 2<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In dieser Variante beziehen wir das Pivot-Element in den Tauschvorgang ein und tauschen Elemente, die <em>gr\u00f6\u00dfer oder gleich<\/em> dem Pivot-Element sind mit Elementen, die kleiner als das Pivot-Element sind. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wenn wir das Pivot-Element selbst vertauschen, m\u00fcssen wir uns diese Positions\u00e4nderung merken.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Somit befindet sich das Pivot-Element vor dem letzten Schritt der Partitionierung im rechten Bereich und kann ohne weitere Pr\u00fcfung mit dem ersten Element des rechten Bereichs getauscht werden.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Den Quellcode dieser Variante findest Du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/QuicksortVariant1.java\" target=\"_blank\">QuicksortVariant2<\/a>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Algorithmus-Variante 3<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">In dieser Variante belassen wir das Pivot-Element w\u00e4hrend der Partitionierung zun\u00e4chst an seinem Platz. Dies erreichen wir, in dem wir nur Elemente, die <em>gr\u00f6\u00dfer<\/em> als das Pivot-Element sind mit Elementen tauschen, die <em>kleiner<\/em> als das Pivot-Element sind.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im letzten Schritt der Partitionierung m\u00fcssen wir dann pr\u00fcfen, ob sich das Pivot-Element im linken oder rechten Bereich befindet. Befindet es sich im linken Bereich, m\u00fcssen wir es mit dem letzten Element des linken Bereichs tauschen; befindet es sich im rechten Bereich, m\u00fcssen wir es mit dem ersten Element des rechten Bereichs tauschen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Den Quellcode dieser Variante findest Du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/QuicksortVariant1.java\" target=\"_blank\">QuicksortVariant3<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-zeitkomplexitaet\">Quicksort Zeitkomplexit\u00e4t<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Klicke auf den folgenden Link f\u00fcr eine Einf\u00fchrung in <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">\"Zeitkomplexit\u00e4t\" und \"O-Notation\"<\/a> (mit Beispielen und Diagrammen).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir bezeichnen im Folgenden die Anzahl der zu sortierenden Elemente mit <em>n<\/em>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-im-best-case\">Zeitkomplexit\u00e4t im best case<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Quicksort erreicht optimale Performance, wenn wir die Arrays und Teil-Arrays immer wieder in zwei gleich gro\u00dfe Partitionen aufteilen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Denn dann brauchen wir bei einer Verdopplung der Anzahl der Elemente <em>n<\/em> nur eine einzige zus\u00e4tzliche Stufe von Partitionierungen <em>p<\/em>. Folgendes Diagramm zeigt, dass bei vier Elementen zwei Partitionierungsstufen ben\u00f6tigt werden und bei acht Elementen nur eine mehr:<\/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=\"562\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity.png\" alt=\"Quicksort - Zeitkomplexit\u00e4t im best case - Anzahl der Partitionierungsstufen\" class=\"wp-image-14883\" style=\"width:550px;height:281px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity.png 1100w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-224x114.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-336x172.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-504x257.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-672x343.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-400x204.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-600x307.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-800x409.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity-944x482.png 944w\" sizes=\"(max-width: 1100px) 100vw, 1100px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Wir haben also eine Anzahl an Partitionierungsstufen von <em>log<sub>2<\/sub> n<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Auf jeder Partitionierungsstufe m\u00fcssen wir insgesamt <em>n<\/em> Elemente auf linke und rechte Partition aufteilen (auf der ersten Ebene <em>1 \u00d7 n<\/em>, auf der zweiten <em>2 \u00d7 n\/2<\/em>, auf der dritten <em>4 \u00d7 n\/4<\/em>, usw.):<\/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=\"1218\" height=\"562\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2.png\" alt=\"Quicksort - Zeitkomplexit\u00e4t im best case - Aufwand pro Partitionierungsstufe\" class=\"wp-image-14886\" style=\"width:609px;height:281px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2.png 1218w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-224x103.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-336x155.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-504x233.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-672x310.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-400x185.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-600x277.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-800x369.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-944x436.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_best_case_time_complexity_2-1200x554.png 1200w\" sizes=\"(max-width: 1218px) 100vw, 1218px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Diese Aufteilung erfolgt \u2013 aufgrund der einzelnen Schleife innerhalb der Partitionierung \u2013 mit linearem Aufwand: Bei Verdoppelung der Array-Gr\u00f6\u00dfe verdoppelt sich auch der Partitionierungs-Aufwand. Der Gesamtaufwand ist daher auf allen Partitionierungsstufen gleich.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wir haben also <em>n<\/em> Elemente mal <em>log<sub>2<\/sub> n<\/em> Partitionierungsstufen. Damit gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background wp-block-paragraph\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Quicksort betr\u00e4gt im&nbsp;<em>best<\/em> <em>case<\/em>:&nbsp;<em>O(n log n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-im-average-case\">Zeitkomplexit\u00e4t im average case<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die <em>durchschnittliche<\/em> Zeitkomplexit\u00e4t l\u00e4sst sich leider nicht ohne komplizierte Mathematik herleiten. Diese w\u00fcrde den Rahmen dieses Artikels sprengen. Ich verwiese hier auf den <a rel=\"noopener\" href=\"https:\/\/en.wikipedia.org\/wiki\/Quicksort#Average-case_analysis\" target=\"_blank\">englischsprachigen Wikipedia-Artikel<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Dieser kommt zu dem Schluss, dass die durchschnittlich Anzahl der Vergleichsoperationen <em>1,39 n&nbsp;\u00d7 log<sub>2<\/sub>&nbsp;n<\/em> betr\u00e4gt \u2013 wir befinden uns also nach wie vor im quasilinearen Aufwand; es gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background wp-block-paragraph\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Quicksort betr\u00e4gt auch im&nbsp;<em>average case<\/em>:&nbsp;<em>O(n log n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-im-worst-case\">Zeitkomplexit\u00e4t im worst case<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Wenn das Pivot-Element immer das kleinste oder gr\u00f6\u00dfte Element des (Teil-)Arrays ist (z. B. weil unsere Eingabedaten bereits sortiert sind und wir als Pivot-Element immer das letzte w\u00e4hlen), w\u00fcrde das Array nicht in zwei etwa gleich gro\u00dfe Partitionen aufgeteilt werden, sondern in eine der L\u00e4nge <em>0<\/em> (da kein Element gr\u00f6\u00dfer als das Pivot-Element ist) und eine der L\u00e4nge <em>n-1<\/em> (alle Elemente bis auf das Pivot-Element).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Damit br\u00e4uchten wir <em>n<\/em> Partitionierungsstufen mit einem Partitionierungsaufwand der Gr\u00f6\u00dfe <em>n, n-1, n-2<\/em>, usw:<\/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=\"1156\" height=\"562\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity.png\" alt=\"Quicksort - Zeitkomplexit\u00e4t im worst case\" class=\"wp-image-14888\" style=\"width:578px;height:281px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity.png 1156w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-224x109.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-336x163.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-504x245.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-672x327.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-400x194.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-600x292.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-800x389.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_worst_case_time_complexity-944x459.png 944w\" sizes=\"(max-width: 1156px) 100vw, 1156px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Der Partitionierungsaufwand sinkt linear von <em>n<\/em> bis <em>0<\/em> \u2013 im Mittel betr\u00e4gt er also <em>\u00bd n<\/em>. Bei <em>n<\/em> Partitionierungsstufen betr\u00e4gt der Gesamtaufwand also <em>n \u00d7 \u00bd n = \u00bd n\u00b2<\/em>. Es gilt somit:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background wp-block-paragraph\" style=\"background-color:#e7f2f8\">Die Zeitkomplexit\u00e4t von Quicksort betr\u00e4gt im worst case: <em>O(n\u00b2)<\/em><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In der Praxis w\u00fcrde der Versuch ein aufsteigend oder absteigend vorsortiertes Array mit der Pivot-Strategie \"rechtes Element\" zu sortieren sehr schnell an einer <code>StackOverflowException<\/code> scheitern, da die Rekursion so tief gehen m\u00fcsste wie das Array gro\u00df ist.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"java-quicksort-laufzeit\">Java Quicksort Laufzeit<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Nach so viel Theorie zur\u00fcck zur Praxis!<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Mit dem Programm <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\">UltimateTest<\/a> k\u00f6nnen wir die tats\u00e4chliche Performance von Quicksort (und allen anderen Algorithmen dieser Artikelserie) messen. Das Programm geht dabei wie folgt vor:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Es sortiert Arrays der Gr\u00f6\u00dfe 1.024, 2.048, 4.096, usw. bis maximal 536.870.912 (= 2<sup>29<\/sup>), bricht dabei allerdings ab, wenn ein einzelner Sortiervorgang 20 Sekunden oder l\u00e4nger ben\u00f6tigt.<\/li>\n\n\n\n<li>Es wendet den Sortieralgorithmus auf unsortierte Eingabedaten, aufsteigend sortierte und absteigend sortierte Eingabedaten an.<\/li>\n\n\n\n<li>Es durchl\u00e4uft zun\u00e4chst zwei Warmup-Phasen, um dem HotSpot-Compiler ausreichend Zeit zu geben, den Code zu optimieren.<\/li>\n\n\n\n<li>Das ganze wird so oft wiederholt, bis der Prozess beendet wird.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-messung-der-quicksort-algorithmus-varianten\">Laufzeit-Messung der Quicksort-Algorithmus-Varianten<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Zun\u00e4chst m\u00fcssen wir entscheiden, welche Algorithmus-Variante wir ins Rennen schicken wollen, um den Test nicht ausufern zu lassen. Daf\u00fcr kombiniert das Programm <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/comparisons\/CompareQuicksorts.java\">CompareQuicksorts<\/a> alle Varianten mit allen Pivot-Strategien und sortiert mit jeder Kombination 50 mal etwa 5,5 Millionen Elemente.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hier ist das Ergebnis, sortiert nach Laufzeit (Datei <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-18\/Quicksort_Pivot_Strategies.log\">Quicksort_Pivot_Strategies.log<\/a>):<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><thead><tr><th>Variante<\/th><th class=\"has-text-align-center\" data-align=\"center\">Pivot-Strategie<\/th><th class=\"has-text-align-right\" data-align=\"right\">Median<\/th><\/tr><\/thead><tbody><tr><td>QuicksortSimple<\/td><td class=\"has-text-align-center\" data-align=\"center\">RIGHT<\/td><td class=\"has-text-align-right\" data-align=\"right\">458,5 ms<\/td><\/tr><tr><td>QuicksortVariant1<\/td><td class=\"has-text-align-center\" data-align=\"center\">RIGHT<\/td><td class=\"has-text-align-right\" data-align=\"right\">460,4 ms<\/td><\/tr><tr><td>QuicksortVariant1<\/td><td class=\"has-text-align-center\" data-align=\"center\">MIDDLE<\/td><td class=\"has-text-align-right\" data-align=\"right\">461,7 ms<\/td><\/tr><tr><td>QuicksortVariant3<\/td><td class=\"has-text-align-center\" data-align=\"center\">RIGHT<\/td><td class=\"has-text-align-right\" data-align=\"right\">472,4 ms<\/td><\/tr><tr><td>QuicksortVariant3<\/td><td class=\"has-text-align-center\" data-align=\"center\">MIDDLE<\/td><td class=\"has-text-align-right\" data-align=\"right\">473,5 ms<\/td><\/tr><tr><td>QuicksortVariant2<\/td><td class=\"has-text-align-center\" data-align=\"center\">RIGHT<\/td><td class=\"has-text-align-right\" data-align=\"right\">477,9 ms<\/td><\/tr><tr><td>QuicksortVariant2<\/td><td class=\"has-text-align-center\" data-align=\"center\">MIDDLE<\/td><td class=\"has-text-align-right\" data-align=\"right\">483,4 ms<\/td><\/tr><tr><td>QuicksortVariant1<\/td><td class=\"has-text-align-center\" data-align=\"center\">MEDIAN3<\/td><td class=\"has-text-align-right\" data-align=\"right\">489,8 ms<\/td><\/tr><tr><td>QuicksortVariant3<\/td><td class=\"has-text-align-center\" data-align=\"center\">MEDIAN3<\/td><td class=\"has-text-align-right\" data-align=\"right\">507,4 ms<\/td><\/tr><tr><td>QuicksortVariant2<\/td><td class=\"has-text-align-center\" data-align=\"center\">MEDIAN3<\/td><td class=\"has-text-align-right\" data-align=\"right\">508,6 ms<\/td><\/tr><tr><td>QuicksortVariant1<\/td><td class=\"has-text-align-center\" data-align=\"center\">RANDOM<\/td><td class=\"has-text-align-right\" data-align=\"right\">516,1 ms<\/td><\/tr><tr><td>QuicksortVariant3<\/td><td class=\"has-text-align-center\" data-align=\"center\">RANDOM<\/td><td class=\"has-text-align-right\" data-align=\"right\">528,9 ms<\/td><\/tr><tr><td>QuicksortVariant2<\/td><td class=\"has-text-align-center\" data-align=\"center\">RANDOM<\/td><td class=\"has-text-align-right\" data-align=\"right\">534,2 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Folgendes l\u00e4sst sich ablesen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Der simple Algorithmus ist am schnellsten.<\/li>\n\n\n\n<li>F\u00fcr alle Algorithmus-Varianten ist die Pivot-Strategie RIGHT am schnellsten, dicht gefolgt von MIDDLE, danach mit etwas gr\u00f6\u00dferem Abstand MEDIAN3 (der Overhead ist hier offenbar gr\u00f6\u00dfer als der Gewinn), und am langsamsten ist RANDOM (Zufallszahlen zu generieren ist teuer).<\/li>\n\n\n\n<li>F\u00fcr alle Pivot-Strategien ist Variante 1 am schnellsten, Variante 3 am zweitschnellsten und Variante 2 am langsamsten.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"laufzeit-messungen-fuer-verschiedene-pivot-strategien-und-array-groessen\">Laufzeit-Messungen f\u00fcr verschiedene Pivot-Strategien und Array-Gr\u00f6\u00dfen<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Aufgrund dieses Ergebnisses f\u00fchre ich den <em>UltimateTest<\/em> mit Algorithmus-Variante 1 aus (Pivot-Element wird vorab mit dem rechten Element vertauscht).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">In den folgenden Abschnitten findest du die Ergebnisse f\u00fcr die verschiedenen Pivot-Strategien nach 50 Iterationen (dies sind nur Ausz\u00fcge; das vollst\u00e4ndige Testergebnis findest du in <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-18\/UltimateTest_Quicksort.log\">UltimateTest_Quicksort.log<\/a>).<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Messergebnisse f\u00fcr Pivot-Strategie \"rechtes Element\"<\/h4>\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\">1.024<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,051 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,155 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,158 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">2.048<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,100 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,578 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,597 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">4.096<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,208 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2,247 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2,322 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">8.192<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,436 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">8,906 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">9,127 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">16.384<\/td><td class=\"has-text-align-right\" data-align=\"right\">0,920 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">32.768<\/td><td class=\"has-text-align-right\" data-align=\"right\">1,941 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><\/tr><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\">33.554.432<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.099,994 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/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\">6.421,172 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">134.217.728<\/td><td class=\"has-text-align-right\" data-align=\"right\">13.305,377 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/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\">27.493,636 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><td class=\"has-text-align-right\" data-align=\"right\">StackOverflow<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Folgendes l\u00e4sst sich ablesen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Bei zuf\u00e4llig verteilten Eingabedaten verl\u00e4ngert sich die ben\u00f6tigte Zeit um etwas mehr als das doppelte, wenn sich die Gr\u00f6\u00dfe des zu sortierenden Arrays verdoppelt. Dies entspricht der erwarteten quasi-linearen Laufzeit \u2013 <em>O(n log n)<\/em>.<\/li>\n\n\n\n<li>Bei aufsteigend oder absteigend sortierten Eingabedaten vervierfacht sich die ben\u00f6tigte Zeit bei verdoppelter Eingabegr\u00f6\u00dfe, hier haben wir also quadratische Zeit \u2013 <em>O(n\u00b2)<\/em>.<\/li>\n\n\n\n<li>Absteigend sortierte Daten zu sortieren dauert nur wenig l\u00e4nger als aufsteigend sortierte Daten zu sortieren.<\/li>\n\n\n\n<li>Bei nur 8.192 Elementen wird f\u00fcr das Sortieren vorsortierter Eingabedaten bereits 23 mal so lange ben\u00f6tigt wie f\u00fcr das Sortieren unsortierter Daten.<\/li>\n\n\n\n<li>Bei mehr als 8.192 Elementen kommt es bei vorsortierten Eingabedaten zur gef\u00fcrchteten <code>StackOverflowException<\/code>.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Messergebnisse f\u00fcr Pivot-Strategie \"mittleres Element\"<\/h4>\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.777.216<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.508 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">191,3 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">227,0 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">33.554.432<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.127 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">409,5 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">464,7 ms<\/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\">6.486 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">806,4 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">942,9 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">134.217.728<\/td><td class=\"has-text-align-right\" data-align=\"right\">13.409 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.727,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.945,8 ms<\/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\">27.740 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.405,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.959,2 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Es l\u00e4sst sich ablesen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Sowohl f\u00fcr unsortierte als auch sortierte Eingabedaten wird bei Verdoppelung der Array-Gr\u00f6\u00dfe etwas mehr als die doppelte Zeit ben\u00f6tigt. Dies entspricht der erwarteten quasi-linearen Laufzeit \u2013 <em>O(n log n)<\/em>.<\/li>\n\n\n\n<li>F\u00fcr bereits sortierte Eingabedaten ist der Algorithmus deutlich schneller als f\u00fcr zuf\u00e4llig angeordnete \u2013 und zwar sowohl f\u00fcr aufsteigend als auch f\u00fcr absteigend sortierte Daten.<\/li>\n\n\n\n<li>Die Performance-Verlust durch den Vorabtausch des mittleren mit dem rechten Element betr\u00e4gt in allen Tests mit unsortierten Eingabedaten weniger als 0,9 %.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Messergebnisse f\u00fcr Pivot-Strategie \"Median aus drei Elementen\"<\/h4>\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.777.216<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.589 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">222,6 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">249,0 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">33.554.432<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.291 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">473,2 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">514,4 ms<\/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\">6.807 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">934,6 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.039,1 ms<\/td><\/tr><tr><td class=\"has-text-align-right\" data-align=\"right\">134.217.728<\/td><td class=\"has-text-align-right\" data-align=\"right\">14.066 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">1.980,5 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">2.142,8 ms<\/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\">29.041 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">3.907,6 ms<\/td><td class=\"has-text-align-right\" data-align=\"right\">4.349,2 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Es l\u00e4sst sich ablesen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Auch hier haben wir in allen F\u00e4llen quasi-linearen Aufwand \u2013 <em>O(n log n)<\/em>.<\/li>\n\n\n\n<li>Wie schon beim Vergleich der Algorithmus-Varianten ist die Pivot-Strategie \"Median aus drei Elementen\" etwas langsamer als die Strategie \"mittleres Element\".<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">\u00dcberblick \u00fcber alle Messergebnisse<\/h4>\n\n\n\n<p class=\"wp-block-paragraph\">Hier findest du die Messergebnisse noch einmal als Diagramm (absteigend sortierte Eingabedaten habe ich der \u00dcbersicht halber weggelassen):<\/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=\"1520\" height=\"824\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2.png\" alt=\"Quicksort-Laufzeit bei verschiedenen Pivot-Strategien\" class=\"wp-image-14878\" style=\"width:760px;height:412px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2.png 1520w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-224x121.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-336x182.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-504x273.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-672x364.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-400x217.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-600x325.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-800x434.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-944x512.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_pivot_strategies_v2-1200x651.png 1200w\" sizes=\"(max-width: 1520px) 100vw, 1520px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Man sieht noch einmal sch\u00f6n, dass die Strategie \"Rechtes Element\" f\u00fcr aufsteigend sortierte Daten zu quadratischem Aufwand f\u00fchrt (rote Linie) und f\u00fcr unsortierte Daten am schnellsten ist (blaue Linie). Am zweitschnellsten (mit minimalem Abstand) ist die Pivot-Stragie \"Mittleres Element\" (gelbe Linie).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-optimiert-kombination-mit-insertion-sort\">Quicksort optimiert: Kombination mit Insertion Sort<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr sehr kleine Arrays ist Insertion Sort schneller als Quicksort, daher werden in der Praxis diese Algorithmen h\u00e4ufig kombiniert. D. h. (Sub-)Arrays werden ab einer bestimmten Gr\u00f6\u00dfe nicht weiter partitioniert, sondern mit Insertion Sort sortiert.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-insertion-sort-quellcode\">Quicksort\/Insertion Sort Quellcode<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die Quellcode-\u00c4nderungen gegen\u00fcber des Standard-Quicksorts sind sehr \u00fcberschaubar und beschr\u00e4nken sich auf die <code>quicksort()<\/code>-Methode. Hier noch einmal die Methode aus dem Standard-Algorithmus:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">quicksort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ End of recursion reached?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (left &gt;= right) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-keyword\">int<\/span> pivotPos = partition(elements, left, right);\n  quicksort(elements, left, pivotPos - <span class=\"hljs-number\">1<\/span>);\n  quicksort(elements, pivotPos + <span class=\"hljs-number\">1<\/span>, right);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><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 class=\"wp-block-paragraph\">Und hier die optimierte Variante, wobei die Variablen <code>insertionSort<\/code> und <code>partitioningAlgorithm<\/code> Instanzen des Insertion-Sort- und des Quicksort-Algorithmus sind. Hinzugekommen ist hier lediglich der mit <em>\"Threshold for insertion sort reached?\"<\/em> kommentierte Code-Block in der Mitte der Methode:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">quicksort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ End of recursion reached?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (left &gt;= right) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Threshold for insertion sort reached?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (right - left &lt; threshold) {\n    insertionSort.sort(elements, left, right + <span class=\"hljs-number\">1<\/span>);\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-keyword\">int<\/span> pivotPos = partitioningAlgorithm.partition(elements, left, right);\n  quicksort(elements, left, pivotPos - <span class=\"hljs-number\">1<\/span>);\n  quicksort(elements, pivotPos + <span class=\"hljs-number\">1<\/span>, right);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><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 class=\"wp-block-paragraph\">Den kompletten Quellcode findest du in der Klasse <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/QuicksortImproved.java\" target=\"_blank\">QuicksortImproved<\/a> im GitHub-Repository. Als Konstruktorparameter wird der Grenzwert f\u00fcr das Umschalten auf Insertion Sort, <code>threshold<\/code>, \u00fcbergeben, sowie eine Instanz der zu verwendenden Quicksort-Variante.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-insertion-sort-performance\">Quicksort\/Insertion Sort Performance<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Das Programm <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/comparisons\/CompareImprovedQuicksort.java\" target=\"_blank\" rel=\"noopener\">CompareImprovedQuickSort<\/a> misst die ben\u00f6tigte Zeit zum Sortieren von etwa 5,5 Millionen Elementen bei verschiedenen Grenzwerten f\u00fcr das Umschalten auf Insertion Sort.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Da das optimierte Quicksort nur Arrays ab einer gewissen Gr\u00f6\u00dfe partitioniert, k\u00f6nnte der Einfluss der Pivot-Strategie und der Algorithmus-Variante eine andere Rolle spielen als bisher. Um dies zu ber\u00fccksichtigen, testet das Programm die Grenzwerte f\u00fcr alle drei Algorithmus-Varianten sowie die Pivot-Strategien \"Mitte\" und \"Median aus drei Elementen\".<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die kompletten Messergebnisse findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-18\/CompareImprovedQuicksort.log\" target=\"_blank\">CompareImprovedQuicksort.log<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wie auch in den vorangegangenen Tests performen hier Algorithmus-Variante 1 und Pivot-Strategie \"Mittleres Element\" durchgehend am besten. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hier die Messwerte f\u00fcr die gew\u00e4hlte Kombination und verschiedene Grenzwerte f\u00fcr das Umschalten auf Insertion Sort:<\/p>\n\n\n\n<figure class=\"wp-block-table aligncenter is-style-stripes\"><table><thead><tr><th>Grenzwert<\/th><th class=\"has-text-align-right\" data-align=\"right\">Laufzeit<\/th><\/tr><\/thead><tbody><tr><td>0 (= regul\u00e4res Quicksort)<\/td><td class=\"has-text-align-right\" data-align=\"right\">492,6 ms<\/td><\/tr><tr><td>2<\/td><td class=\"has-text-align-right\" data-align=\"right\">492,6 ms<\/td><\/tr><tr><td>4<\/td><td class=\"has-text-align-right\" data-align=\"right\">476,1 ms<\/td><\/tr><tr><td>8<\/td><td class=\"has-text-align-right\" data-align=\"right\">456,1 ms<\/td><\/tr><tr><td>16<\/td><td class=\"has-text-align-right\" data-align=\"right\">436,0 ms<\/td><\/tr><tr><td>24<\/td><td class=\"has-text-align-right\" data-align=\"right\">427,2 ms<\/td><\/tr><tr><td>32<\/td><td class=\"has-text-align-right\" data-align=\"right\">423,1 ms<\/td><\/tr><tr><td>48<\/td><td class=\"has-text-align-right\" data-align=\"right\">422,3 ms<\/td><\/tr><tr><td>64<\/td><td class=\"has-text-align-right\" data-align=\"right\">425,3 ms<\/td><\/tr><tr><td>96<\/td><td class=\"has-text-align-right\" data-align=\"right\">438,0 ms<\/td><\/tr><tr><td>128<\/td><td class=\"has-text-align-right\" data-align=\"right\">454,9 ms<\/td><\/tr><tr><td>196<\/td><td class=\"has-text-align-right\" data-align=\"right\">493,4 ms<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">Hier die Messwerte in grafischer Darstellung:<\/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=\"1528\" height=\"796\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds.png\" alt=\"Umschaltung von Quicksort zu Insertion Sort bei verschiedenen Grenzwerten\" class=\"wp-image-14869\" style=\"width:764px;height:398px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds.png 1528w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-224x117.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-336x175.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-504x263.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-672x350.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-400x208.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-600x313.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-800x417.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-944x492.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_switching_to_Insertion_Sort_thresholds-1200x625.png 1200w\" sizes=\"(max-width: 1528px) 100vw, 1528px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Resultat:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Durch das Umschalten auf Insertion Sort f\u00fcr (Sub-)Arrays, die 48 oder weniger Elemente enthalten, k\u00f6nnen wir die Laufzeit von Quicksort bei 5,5 Millionen Elementen auf etwa 85 % des urspr\u00fcnglichen Wertes reduzieren.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Wie sich der optimierte Quicksort-Algorithmus bei anderen Eingabegr\u00f6\u00dfen schl\u00e4gt, erf\u00e4hrst du im Abschnitt <a href=\"#Vergleich_aller_Quicksort-Optimierungen\">\"Vergleich aller Quicksort-Optimierungen\"<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"dual-pivot-quicksort\">Dual-Pivot Quicksort<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Quicksort l\u00e4sst sich noch weiter optimieren, in dem man nicht <em>ein<\/em> Pivot-Element verwendet, sondern <em>zwei<\/em>. Bei der Partitionierung werden die Elemente dann aufgeteilt in:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Elemente kleiner als das kleinere Pivot-Element,<\/li>\n\n\n\n<li>Elemente gr\u00f6\u00dfer als\/gleich wie das kleinere Pivot-Element und kleiner als das gr\u00f6\u00dfere Pivot-Element,<\/li>\n\n\n\n<li>Elemente gr\u00f6\u00dfer als\/gleich wie das gr\u00f6\u00dfere Pivot-Element.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Auch hier gibt es unterschiedliche Pivot-Strategien, z. B.:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Linkes und rechtes Element: Dies f\u00fchrt \u2013 analog zum regul\u00e4ren Quicksort \u2013 dazu, dass bei sortierten Elementen zwei Partitionen leer bleiben und eine Partition <em>n-2<\/em> Elemente enth\u00e4lt. Dies wiederum resultiert in quadratischem Aufwand und <code>StackOverflowExceptions<\/code> schon bei vergleichsweise kleinen <em>n<\/em>.<\/li>\n\n\n\n<li>Elemente an den Position \"ein Drittel\" und \"zwei Drittel\": Dies ist vergleichbar mit der Strategie \"Mittleres Element\" im regul\u00e4ren Quicksort.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Das folgende Diagramm zeigt eine beispielhafte Partitionierung mit zwei Pivot-Elementen an den \"Drittel\"-Positionen:<\/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=\"1560\" height=\"894\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning.png\" alt=\"Partitionierung bei Dual-Pivot Quicksort\" class=\"wp-image-14903\" style=\"width:780px;height:447px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning.png 1560w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-336x193.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-800x458.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-944x541.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_Partitioning-1200x688.png 1200w\" sizes=\"(max-width: 1560px) 100vw, 1560px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Dual-Pivot Quicksort wird (mit zus\u00e4tzlichen Optimierungen) im JDK von der Methode <code>Arrays.sort()<\/code> eingesetzt.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"dual-pivot-quicksort-quellcode\">Dual-Pivot Quicksort Quellcode<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Die <code>quicksort()<\/code>-Methode ruft sich \u2013 im Vergleich zum regul\u00e4ren Algorithmus \u2013 nicht f\u00fcr zwei, sondern f\u00fcr drei Partitionen rekursiv auf:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">quicksort<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ End of recursion reached?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (left &gt;= right) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-keyword\">int<\/span>&#091;] pivotPos = partition(elements, left, right);\n  <span class=\"hljs-keyword\">int<\/span> p0 = pivotPos&#091;<span class=\"hljs-number\">0<\/span>];\n  <span class=\"hljs-keyword\">int<\/span> p1 = pivotPos&#091;<span class=\"hljs-number\">1<\/span>];\n  quicksort(elements, left, p0 - <span class=\"hljs-number\">1<\/span>);\n  quicksort(elements, p0 + <span class=\"hljs-number\">1<\/span>, p1 - <span class=\"hljs-number\">1<\/span>);\n  quicksort(elements, p1 + <span class=\"hljs-number\">1<\/span>, right);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><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 class=\"wp-block-paragraph\">Die <code>partition()<\/code>-Methode ruft zun\u00e4chst <code>findPivotsAndMoveToLeftRight()<\/code> auf, welche anhand der gew\u00e4hlten Pivot-Strategie die Pivot-Elemente ausw\u00e4hlt und mit den Elementen links und rechts vertauscht (analog zum Vertauschen des Pivot-Elements mit dem rechten Elemente im regul\u00e4ren Quicksort).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Danach laufen wieder zwei Suchzeiger von links und rechts \u00fcber das Array und vergleichen und tauschen die Elemente, so dass diese am Ende auf drei Partitionen aufgeteilt sind. Wie genau sie das tun, l\u00e4sst sich anhand der sprechenden Variablennamen einigerma\u00dfen gut am Quellcode ablesen.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">int<\/span>&#091;] partition(<span class=\"hljs-keyword\">int<\/span>&#091;] elements, <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right) {\n  findPivotsAndMoveToLeftRight(elements, left, right);\n  <span class=\"hljs-keyword\">int<\/span> leftPivot = elements&#091;left];\n  <span class=\"hljs-keyword\">int<\/span> rightPivot = elements&#091;right];\n\n  <span class=\"hljs-keyword\">int<\/span> leftPartitionEnd = left + <span class=\"hljs-number\">1<\/span>;\n  <span class=\"hljs-keyword\">int<\/span> leftIndex = left + <span class=\"hljs-number\">1<\/span>;\n  <span class=\"hljs-keyword\">int<\/span> rightIndex = right - <span class=\"hljs-number\">1<\/span>;\n\n  <span class=\"hljs-keyword\">while<\/span> (leftIndex &lt;= rightIndex) {\n\n    <span class=\"hljs-comment\">\/\/ elements &lt; left pivot element?<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (elements&#091;leftIndex] &lt; leftPivot) {\n      ArrayUtils.swap(elements, leftIndex, leftPartitionEnd);\n      leftPartitionEnd++;\n    }\n\n    <span class=\"hljs-comment\">\/\/ elements &gt;= right pivot element?<\/span>\n    <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (elements&#091;leftIndex] &gt;= rightPivot) {\n      <span class=\"hljs-keyword\">while<\/span> (elements&#091;rightIndex] &gt; rightPivot &amp;&amp; leftIndex &lt; rightIndex) {\n        rightIndex--;\n      }\n      ArrayUtils.swap(elements, leftIndex, rightIndex);\n      rightIndex--;\n      <span class=\"hljs-keyword\">if<\/span> (elements&#091;leftIndex] &lt; leftPivot) {\n        ArrayUtils.swap(elements, leftIndex, leftPartitionEnd);\n        leftPartitionEnd++;\n      }\n    }\n    leftIndex++;\n  }\n  leftPartitionEnd--;\n  rightIndex++;\n\n  <span class=\"hljs-comment\">\/\/ move pivots to their final positions<\/span>\n  ArrayUtils.swap(elements, left, leftPartitionEnd);\n  ArrayUtils.swap(elements, right, rightIndex);\n\n  <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">new<\/span> <span class=\"hljs-keyword\">int<\/span>&#091;]{leftPartitionEnd, rightIndex};\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><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 class=\"wp-block-paragraph\">Die Methode <code>findPivotsAndMoveToLeftRight()<\/code> arbeitet wie folgt:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bei der Pivot-Strategie <code>LEFT_RIGHT<\/code> pr\u00fcft sie, ob das ganz linke Element kleiner ist als das ganz rechte. Wenn nicht, werden beide vertauscht.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Bei der Strategie <code>THIRDS<\/code> werden zun\u00e4chst die Elemente an den Positionen \"ein Drittel\" (Variable <code>first<\/code>) und \"zwei Drittel\" (Variable <code>second<\/code>) extrahiert. Danach folgt eine Reihe von <code>if<\/code>-Abfragen, die letztendlich blo\u00df das gr\u00f6\u00dfere der beiden Elemente nach ganz rechts setzt und das kleinere der beiden Elemente nach ganz links.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">(Der Code wird dadurch so aufgebl\u00e4ht, dass zwei Sonderf\u00e4lle ber\u00fccksichtigt werden m\u00fcssen: In sehr kleinen Partitionen k\u00f6nnte das erste Pivotelement auf das ganz linke Element fallen und das zweite Pivotelement auf das ganz rechte Element.)<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">findPivotsAndMoveToLeftRight<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span>&#091;] elements,\n                                          <span class=\"hljs-keyword\">int<\/span> left, <span class=\"hljs-keyword\">int<\/span> right)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">switch<\/span> (pivotStrategy) {\n    <span class=\"hljs-keyword\">case<\/span> LEFT_RIGHT -&gt; {\n      <span class=\"hljs-keyword\">if<\/span> (elements&#091;left] &gt; elements&#091;right]) {\n        ArrayUtils.swap(elements, left, right);\n      }\n    }\n\n    <span class=\"hljs-keyword\">case<\/span> THIRDS -&gt; {\n      <span class=\"hljs-keyword\">int<\/span> len = right - left + <span class=\"hljs-number\">1<\/span>;\n      <span class=\"hljs-keyword\">int<\/span> firstPos = left + (len - <span class=\"hljs-number\">1<\/span>) \/ <span class=\"hljs-number\">3<\/span>;\n      <span class=\"hljs-keyword\">int<\/span> secondPos = right - (len - <span class=\"hljs-number\">2<\/span>) \/ <span class=\"hljs-number\">3<\/span>;\n\n      <span class=\"hljs-keyword\">int<\/span> first = elements&#091;firstPos];\n      <span class=\"hljs-keyword\">int<\/span> second = elements&#091;secondPos];\n\n      <span class=\"hljs-keyword\">if<\/span> (first &gt; second) {\n        <span class=\"hljs-keyword\">if<\/span> (secondPos == right) {\n          <span class=\"hljs-keyword\">if<\/span> (firstPos == left) {\n            ArrayUtils.swap(elements, left, right);\n          } <span class=\"hljs-keyword\">else<\/span> {\n            <span class=\"hljs-comment\">\/\/ 3-way swap<\/span>\n            elements&#091;right] = first;\n            elements&#091;firstPos] = elements&#091;left];\n            elements&#091;left] = second;\n          }\n        } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (firstPos == left) {\n          <span class=\"hljs-comment\">\/\/ 3-way swap<\/span>\n          elements&#091;left] = second;\n          elements&#091;secondPos] = elements&#091;right];\n          elements&#091;right] = first;\n        } <span class=\"hljs-keyword\">else<\/span> {\n          ArrayUtils.swap(elements, firstPos, right);\n          ArrayUtils.swap(elements, secondPos, left);\n        }\n      } <span class=\"hljs-keyword\">else<\/span> {\n        <span class=\"hljs-keyword\">if<\/span> (secondPos != right) {\n          ArrayUtils.swap(elements, secondPos, right);\n        }\n        <span class=\"hljs-keyword\">if<\/span> (firstPos != left) {\n          ArrayUtils.swap(elements, firstPos, left);\n        }\n      }\n    }\n\n    <span class=\"hljs-keyword\">default<\/span> -&gt; <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException(<span class=\"hljs-string\">\"Unexpected value: \"<\/span> + pivotStrategy);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><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 class=\"wp-block-paragraph\">Den vollst\u00e4ndigen Quellcode findest Du in der Datei <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/DualPivotQuicksort.java\" target=\"_blank\">DualPivotQuicksort<\/a>. <\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"dual-pivot-quicksort-performance\">Dual-Pivot Quicksort Performance<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Ob und inwieweit Dual-Pivot Quicksort die Performance verbessert, findest du im Abschnitt <a href=\"#Vergleich_aller_Quicksort-Optimierungen\">\"Vergleich aller Quicksort-Optimierungen\"<\/a> heraus.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"dual-pivot-quicksort-kombiniert-mit-insertion-sort\">Dual-Pivot Quicksort kombiniert mit Insertion Sort<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Genau wie das regul\u00e4re Quicksort kann auch Dual-Pivot Quicksort mit Insertion Sort kombiniert werden. Die Quellcode-\u00c4nderungen entsprechen denen f\u00fcr das regul\u00e4re Quicksort (s. Abschnitt <a href=\"#QuicksortInsertion_Sort_Quellcode\">\"Quicksort\/Insertion Sort Quellcode\"<\/a>). Ich gehe daher hier nicht noch einmal im Detail darauf ein.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Den Quellcode findest du in <a href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/method\/quicksort\/DualPivotQuicksortImproved.java\" target=\"_blank\" rel=\"noopener\">DualPivotQuicksortImproved<\/a>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Das Programm <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/src\/main\/java\/eu\/happycoders\/sort\/demos\/comparisons\/CompareImprovedDualPivotQuicksort.java\" target=\"_blank\">CompareImprovedDualPivotQuicksort<\/a> testet den Algorithmus f\u00fcr verschiedene Grenzwerte f\u00fcr das Umschalten auf Insertion Sort. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Messwerte findest du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-18\/CompareImprovedDualPivotQuicksort.log\" target=\"_blank\">CompareImprovedDualPivotQuicksort.log<\/a>. Hier sind sie 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=\"1528\" height=\"796\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds.png\" alt=\"Umschaltung von Dual-Pivot Quicksort zu Insertion Sort bei verschiedenen Grenzwerten\" class=\"wp-image-14913\" style=\"width:764px;height:398px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds.png 1528w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-224x117.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-336x175.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-504x263.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-672x350.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-400x208.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-600x313.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-800x417.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-944x492.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Dual_Pivot_Quicksort_switching_to_Insertion_Sort_thresholds-1200x625.png 1200w\" sizes=\"(max-width: 1528px) 100vw, 1528px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Es lohnt sich also bei Dual-Pivot-Quicksort (Sub-)Arrays mit 64 Elementen oder weniger mit Insertion Sort zu sortieren.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"vergleich-aller-quicksort-optimierungen\">Vergleich aller Quicksort-Optimierungen<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Mit dem in Abschnitt <a href=\"#Java_Quicksort_Laufzeit\">\"Java Quicksort Laufzeit\"<\/a> erw\u00e4hnten <em>UltimateTest<\/em> vergleiche ich abschlie\u00dfend noch einmal die Performance folgender Algorithmen:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Regul\u00e4res Quicksort mit Pivot-Strategie \"Mittleres Element\",<\/li>\n\n\n\n<li>Quicksort kombiniert mit Insertion Sort und einem Schwellwert von 48,<\/li>\n\n\n\n<li>Dual-Pivot Quicksort mit Pivot-Strategie \"Elemente an den Positionen ein Drittel und zwei Drittel\",<\/li>\n\n\n\n<li>Dual-Pivot Quicksort kombiniert mit Insertion Sort und einem Schwellwert von 64,<\/li>\n\n\n\n<li><code>Arrays.sort()<\/code> des JDK (die JDK-Entwickler haben ihren Dual-Pivot Quicksort-Algorithmus so weit optimiert, dass es sich bei diesem schon bei 44 Elementen lohnt auf Insertion Sort umzuschalten).<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Das Ergebnis findest Du in <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/sorting-algorithms-ultimate-guide\/blob\/main\/results\/2020-07-18\/UltimateTest_Quicksort_Optimized.log\" target=\"_blank\">UltimateTest_Quicksort_Optimized.log<\/a> \u2013 und in folgendem 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=\"1496\" height=\"972\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2.png\" alt=\"Performance von Quicksort kombiniert mit Insertion Sort und Dual-Pivot Quicksort\" class=\"wp-image-14928\" style=\"width:748px;height:486px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2.png 1496w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-224x146.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-336x218.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-504x327.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-672x437.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-400x260.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-600x390.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-800x520.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-944x613.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_runtime_for_various_optimizations-v2-1200x780.png 1200w\" sizes=\"(max-width: 1496px) 100vw, 1496px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Zun\u00e4chst einmal ist sehr sch\u00f6n der quasi-lineare Aufwand aller Varianten zu erkennen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Performance von Dual-Pivot-Quicksort ist sichtbar besser als die des regul\u00e4ren Quicksort \u2013 bei einer Viertelmilliarde Elemente etwa 5 %. Die Kombinationen mit Insertion Sort bringen jeweils mindestens 10 % Performancegewinn.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">An die Sortiermethode des JDK kommen die Eigenimplementierungen nicht ganz heran \u2013 es fehlen noch etwa 6 %. Die JDK-Methode wurde im Laufe der Jahre hoch optimiert. Wenn dich interessiert, wie genau, dann kannst du dir den <a rel=\"noopener\" href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/java.base\/share\/classes\/java\/util\/DualPivotQuicksort.java\" target=\"_blank\">Quellcode auf GitHub<\/a> anschauen.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Au\u00dferdem ist gut zu erkennen, dass alle Varianten vorsortierte Daten deutlich schneller sortieren als unsortierte \u2013 und aufsteigend sortierte Daten etwas schneller als absteigend sortierte. <code>Arrays.sort()<\/code> ist auch f\u00fcr vorsortierte Daten optimiert, so dass die entsprechende Linie nur minimal \u00fcber der Null-Linie liegt (172,7 ms bei einer Viertelmilliarde Elemente).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"weitere-eigenschaften-von-quicksort\">Weitere Eigenschaften von Quicksort<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Als weitere Eigenschaften werden in diesem Kapitel die Platzkomplexit\u00e4t von Quicksort betrachtet, die Stabilit\u00e4t sowie die Parallelisierbarkeit.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"platzkomplexitaet-von-quicksort\">Platzkomplexit\u00e4t von Quicksort<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr jede Rekursionsstufe brauchen wir zus\u00e4tzlichen Speicher auf dem Stack. Im <em>average<\/em> und <em>best case<\/em> ist die maximale Rekursionstiefe durch <em>O(log n)<\/em> begrenzt (s. Abschnitt <a href=\"#Quicksort_Zeitkomplexitaet\">\"Zeitkomplexit\u00e4t\"<\/a>).<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Im <em>worst case<\/em> ist die maximale Rekursionstiefe <em>n<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der Algorithmus kann allerdings durch <a href=\"https:\/\/de.wikipedia.org\/wiki\/Endrekursion\" target=\"_blank\" rel=\"noopener\">Endrekursion<\/a> insoweit optimiert werden, dass immer nur die kleinere Partition durch Rekursion weiterverarbeitet wird und die gr\u00f6\u00dfere durch Iteration.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Da die kleinere Teilpartition maximal halb so gro\u00df ist wie die Ausgangspartition (andernfalls w\u00e4re sie nicht die kleinere, sondern die gr\u00f6\u00dfere Teilpartition), kommt es mit Endrekursion auch im <em>worst case<\/em> maximal zu einer Rekursionstiefe von <em>log<sub>2<\/sub> n<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Der zus\u00e4tzliche Speicherbedarf pro Rekursionsstufe ist konstant. Somit gilt:<\/p>\n\n\n\n<p class=\"has-text-align-center has-background wp-block-paragraph\" style=\"background-color:#e7f2f8\">Die Platzkomplexit\u00e4t von Quicksort ist im <em>best<\/em> und <em>average case<\/em> und \u2013 bei Einsatz von Endrekursion auch im <em>worst case<\/em> \u2013 <em>O(log n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"stabilitaet-von-quicksort\">Stabilit\u00e4t von Quicksort<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Durch die Art und Weise, wie Elemente innerhalb der Partitionierung auf die Teilbereiche aufgeteilt werden, k\u00f6nnen Elemente mit gleichem Key ihre urspr\u00fcngliche Reihenfolge \u00e4ndern.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Hier ein simples Beispiel: Partitioniert werden soll das Array [7, 8, 7, 2, 6] mit der Pivot-Strategie \"Rechtes Element\". (Die zweite 7 habe ich als 7' gekennzeichnet, um sie von der ersten unterscheiden zu k\u00f6nnen.)<\/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=\"1092\" height=\"664\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1.png\" alt=\"Quicksort Stabilit\u00e4t - Schritt 1\" class=\"wp-image-14892\" style=\"width:546px;height:332px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1.png 1092w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-224x136.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-336x204.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-504x306.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-672x409.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-400x243.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-600x365.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-800x486.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step1-944x574.png 944w\" sizes=\"(max-width: 1092px) 100vw, 1092px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Das erste Element von links, das gr\u00f6\u00dfer als die 6 ist, ist die erste 7. Das erste Element von rechts, das kleiner als die 6 ist, ist die 2. Es m\u00fcssen also die erste 7 und die 2 vertauscht werden:<\/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=\"1092\" height=\"772\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2.png\" alt=\"Quicksort Stabilit\u00e4t - Schritt 2\" class=\"wp-image-14893\" style=\"width:546px;height:386px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2.png 1092w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-224x158.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-336x238.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-504x356.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-672x475.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-400x283.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-600x424.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-800x566.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step2-944x667.png 944w\" sizes=\"(max-width: 1092px) 100vw, 1092px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Die erste 7 befindet sich danach nicht mehr vor, sondern hinter der zweiten 7 (7'). Dies bleibt auch so, nachdem das erste Element der rechten Partition (die 8) mit dem Pivot-Element (der 6) vertauscht wurde:<\/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=\"1092\" height=\"746\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3.png\" alt=\"Quicksort Stabilit\u00e4t - Schritt 3\" class=\"wp-image-14894\" style=\"width:546px;height:373px\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3.png 1092w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-224x153.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-336x230.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-504x344.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-672x459.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-400x273.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-600x410.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-800x547.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/Quicksort_stability_step3-944x645.png 944w\" sizes=\"(max-width: 1092px) 100vw, 1092px\" \/><\/figure>\n<\/div>\n\n\n<p class=\"wp-block-paragraph\">Quicksort ist demzufolge nicht stabil.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"parallelisierbarkeit-von-quicksort\">Parallelisierbarkeit von Quicksort<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Es gibt verschiedene Varianten Quicksort zu parallelisieren.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Zum einen lassen sich mehrere Partitionen parallel weiter partitionieren. Bei dieser Variante kann jedoch die erste Partitionierungsstufe gar nicht parallelisiert werden, in der zweiten Stufe k\u00f6nnen nur zwei Cores ausgelastet werden, in der dritten nur vier, usw.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Es gibt mehrere andere, ausgefeiltere Varianten; eine Zusammenfassung findest du in diesem <a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">e<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">n<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">g<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">l<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">i<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">s<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">c<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">hsprachigen<\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\"> <\/a><a rel=\"noreferrer noopener\" href=\"https:\/\/iq.opengenus.org\/parallel-quicksort\/\" target=\"_blank\">Artikel \u00fcber paralleles Quicksort<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"quicksort-vs-mergesort\"><strong>Quicksort vs. Mergesort<\/strong><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Einen Vergleich der Laufzeiten von Quicksort und Mergesort findest du im <a href=\"\/de\/algorithmen\/mergesort\/#Mergesort_vs_Quicksort\">Artikel \u00fcber Mergesort<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zusamenfassung\">Zusamenfassung<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Quicksort ist ein effizienter, instabiler Sortieralgorithmus mit einer Zeitkomplexit\u00e4t von <em>O(n log n)<\/em> im <em>best<\/em> und <em>average case<\/em> und <em>O(n\u00b2)<\/em> im <em>worst case<\/em>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">F\u00fcr sehr kleine <em>n<\/em> ist Quicksort langsamer als Insertion Sort und wird daher in der Praxis in der Regel mit Insertion Sort kombiniert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Die Methode <code>Arrays.sort()<\/code> im JDK verwendet eine Dual-Pivot Quicksort-Implementierung, die (Teil-)Arrays mit weniger als 44 Elementen mit Insertion Sort sortiert.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Weitere Sortieralgorithmen findest du in der <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<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>Dieser Artikel beschreibt die Funktionsweise von Quicksort, zeigt den Java-Quellcode und erkl\u00e4rt, wie man die Zeitkomplexit\u00e4t bestimmt.<\/p>\n","protected":false},"author":1,"featured_media":43245,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_titles_title":"","_seopress_titles_desc":"Wie funktioniert Quicksort? Mit Illustrationen und Quellcode. Wie bestimmt man die Zeitkomplexit\u00e4t (ohne komplizierte Mathematik)?","_seopress_robots_index":"","_seopress_robots_follow":"","_seopress_robots_imageindex":"","_seopress_robots_snippet":"","_seopress_robots_primary_cat":"none","_seopress_robots_breadcrumbs":"","_seopress_robots_freeze_modified_date":"","_seopress_robots_custom_modified_date":"","_seopress_robots_canonical":"","_seopress_social_fb_title":"","_seopress_social_fb_desc":"","_seopress_social_fb_img":"","_seopress_social_fb_img_attachment_id":0,"_seopress_social_fb_img_width":0,"_seopress_social_fb_img_height":0,"_seopress_social_twitter_title":"","_seopress_social_twitter_desc":"","_seopress_social_twitter_img":"","_seopress_social_twitter_img_attachment_id":0,"_seopress_social_twitter_img_width":0,"_seopress_social_twitter_img_height":0,"_seopress_redirections_value":"","_seopress_redirections_enabled":"","_seopress_redirections_enabled_regex":"","_seopress_redirections_logged_status":"both","_seopress_redirections_param":"","_seopress_redirections_type":301,"_seopress_analysis_target_kw":"quicksort,quick sort","_seopress_news_disabled":"","_seopress_video_disabled":"","_seopress_video":[{"url":"","title":"","desc":"","thumbnail":"","duration":"","rating":"","view_count":"","tag":"","cat":""}],"_seopress_pro_schemas_manual":[{"_seopress_pro_rich_snippets_type":"none"}],"_seopress_pro_rich_snippets_disable_all":"","_seopress_pro_rich_snippets_disable":[],"_seopress_pro_schemas":[],"_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":35079,"_post_count":0,"footnotes":""},"categories":[127],"tags":[129],"class_list":["post-12213","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-sortieralgorithmen"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-java-feature-image.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2020\/07\/quicksort-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":1,"uagb_excerpt":"Dieser Artikel beschreibt die Funktionsweise von Quicksort, zeigt den Java-Quellcode und erkl\u00e4rt, wie man die Zeitkomplexit\u00e4t bestimmt.","public_identification_id":"8b6dac17efcd4acc860e7b9a5fa23ea8","private_identification_id":"87e84453c5c4449280717343e75e718d","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12213","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=12213"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12213\/revisions"}],"predecessor-version":[{"id":52513,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/12213\/revisions\/52513"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/43245"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=12213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=12213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=12213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}