{"id":4827,"date":"2024-08-16T15:30:30","date_gmt":"2024-08-16T15:30:30","guid":{"rendered":"https:\/\/msgprogramator.sk\/?p=4827"},"modified":"2026-02-17T11:45:15","modified_gmt":"2026-02-17T11:45:15","slug":"quick-sort","status":"publish","type":"post","link":"https:\/\/msgprogramator.sk\/de\/quick-sort\/","title":{"rendered":"Quick sort &#8211; schnelles Sortieren mit Pivot in Java"},"content":{"rendered":"<p>Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig f\u00fcr die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten ben\u00f6tigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus h\u00e4ngt von Faktoren wie der Gr\u00f6\u00dfe und den Eigenschaften der Eingabedaten, dem verf\u00fcgbaren Speicher und den Zeit- und Platzanforderungen ab. Um dir die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erkl\u00e4ren und sie in Java programmieren. Heute werden wir uns die schnelle Sortierung mit Pivot ansehen (<strong>quick sort<\/strong>). Bislang haben wir die folgenden Sortieralgorithmen behandelt:<\/p>\n<ul>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/sortieralgorithmen\/\" target=\"_blank\" rel=\"noopener\">Sortieralgorithmen<\/a>: eine Einf\u00fchrung in das Sortieren von Daten,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/bubble-sort\/\" target=\"_blank\" rel=\"noopener\">Bubble sort<\/a> &#8211; Blasen-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/comb-sort\/\" target=\"_blank\" rel=\"noopener\">Comb sort<\/a> &#8211; Kamm-Sortierung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/big-o-notation\/\" target=\"_blank\" rel=\"noopener\">Big O Notation<\/a>: Analyse der Komplexit\u00e4t von Algorithmen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/selection-sort\/\" target=\"_blank\" rel=\"noopener\">Auswahlsortierung<\/a> &#8211; Sortieren nach Auswahl,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/insertion-sort\/\" target=\"_blank\" rel=\"noopener\">Einf\u00fcgungssortierung<\/a> &#8211; Sortieren nach Einf\u00fcgung,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/counting-sort\/\" target=\"_blank\" rel=\"noopener\">Counting sort<\/a> &#8211; Sortieren durch Z\u00e4hlen,<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/heap-sort\/\" target=\"_blank\" rel=\"noopener\">Heap sort<\/a> &#8211; Heap Sortierung<\/li>\n<li><a href=\"https:\/\/msgprogramator.sk\/de\/merge-sort\/\" target=\"_blank\" rel=\"noopener\">Merge sort<\/a> &#8211; Sortieren durch Aufteilen und Zusammenf\u00fchren.<\/li>\n<\/ul>\n<h2>Quick sort Algorithmus<\/h2>\n<p>Quick sort ist ein sehr beliebter, vielseitiger und effizienter Datensortieralgorithmus, der zwischen 1959 und 1961 von dem britischen Informatiker <a href=\"https:\/\/en.wikipedia.org\/wiki\/Tony_Hoare\" target=\"_blank\" rel=\"nofollow noopener\">Tony Hoare<\/a> entwickelt wurde. Wie <a href=\"https:\/\/msgprogramator.sk\/de\/merge-sort\/\" target=\"_blank\" rel=\"noopener\">Merge sort<\/a> verwendet er die Technik<em>&#8222;Teile und herrsche<\/em>&#8222;, deren Grundidee darin besteht, ein komplexes Problem in kleinere Teile zu zerlegen und diese Teile separat zu l\u00f6sen. Quick sort ist interessant, weil es versucht, ein Array-Element zuerst an der richtigen Stelle zu platzieren &#8211; ein sogenannter Pivot, der die besondere Eigenschaft hat, dass alle Array-Elemente, die kleiner als er sind, im linken Teil und alle Array-Elemente, die gr\u00f6\u00dfer als er sind, im rechten Teil liegen. Die Elemente in beiden Teilen sind jedoch noch nicht korrekt sortiert. Da sich der Pivot jedoch an der richtigen Stelle im sortierten Ausgabevektor befindet, kann er als Ort dienen, um das Array in zwei Teile &#8211; Partitionen &#8211; zu unterteilen. Die beiden Teile werden dann als separate Arrays betrachtet, die mit neuen Pivots weiter aufgeteilt werden k\u00f6nnen, bis die Teile nur noch ein Element enthalten. Das Ergebnis der Sortierung ist eine Sammlung der Sortierergebnisse der einzelnen Partitionen. Im Allgemeinen ist Quicksort schneller als Mergesort und Heapsort, vor allem, wenn wir eine zuf\u00e4llige Anordnung von Elementen in einem gro\u00dfen Datensatz haben, der sortiert werden muss. Es sollte jedoch betont werden, dass die Leistung des Algorithmus stark von der richtigen Wahl des Pivots abh\u00e4ngt. Eine ungl\u00fcckliche Wahl des Pivots kann zu einer Zeitkomplexit\u00e4t f\u00fchren, die h\u00f6her ist als die der beiden oben genannten Algorithmen.ok<\/p>\n<h2>Quick sort &#8211; das Prinzip des Algorithmus<\/h2>\n<p>Wie wir bereits erw\u00e4hnt haben, besteht das Ziel des Algorithmus darin, f\u00fcr einen gegebenen Eingabevektor ein Element &#8211; den Pivot &#8211; auszuw\u00e4hlen, das den Vektor optimal in zwei ann\u00e4hernd gro\u00dfe Partitionen unterteilt, wobei alle Elemente links kleiner und rechts gr\u00f6\u00dfer als der Pivot sind. Der ung\u00fcnstigste Fall tritt ein, wenn wir einen Pivot w\u00e4hlen, bei dem (fast) alle Elemente links vom Pivot oder rechts davon liegen. Daher gibt es mehrere Methoden, um einen Pivot auszuw\u00e4hlen. Der schnelle Sortieralgorithmus besteht aus den folgenden Schritten:<\/p>\n<ol>\n<li>Auswahl des Pivotelements,<\/li>\n<li>das Feld neu anordnen,<\/li>\n<li>das Feld in Partitionen zu unterteilen.<\/li>\n<\/ol>\n<h3>Quick sort &#8211; Auswahl des Pivotelements<\/h3>\n<p>Es gibt viele M\u00f6glichkeiten, das Pivot-Element auszuw\u00e4hlen. Zu den einfachsten geh\u00f6ren die Auswahl des ersten Elements, die Auswahl des letzten Elements, die Auswahl eines zuf\u00e4lligen Elements, die Auswahl des mittleren Elements usw. Es gibt auch kompliziertere Versionen der Pivot-Auswahl, bei denen wir zum Beispiel drei Elemente zuf\u00e4llig ausw\u00e4hlen und den Median als Pivot verwenden.<\/p>\n<h3>Quick sort &#8211; Neuordnung der Felder<\/h3>\n<p>Angenommen, wir haben das letzte Element des Arrays als Drehpunkt gew\u00e4hlt. Wir vergleichen nach und nach die Elemente von Anfang an mit dem Drehpunkt. Wenn das aktuelle Array-Element gr\u00f6\u00dfer als der Drehpunkt ist, gehen wir zum n\u00e4chsten Element \u00fcber, wenn das Element kleiner ist, ersetzen wir es durch eines der vorherigen gr\u00f6\u00dferen Elemente. Beim Traversieren ben\u00f6tigen wir zwei Indizes. Der erste Index bestimmt das Element, das gerade mit dem Pivot verglichen wird, der zweite Index bestimmt, wo die Elemente enden, die kleiner als der Pivot sind. Sobald der erste Index den Drehpunkt erreicht, ersetzen wir den Drehpunkt durch das erste Element, das gr\u00f6\u00dfer als der Drehpunkt ist (die aktuelle Position des zweiten Index). Anhand eines Beispiels in Java werden wir nun besser verstehen, wie man mit diesen Indizes arbeitet.<\/p>\n<h3>Quick sort &#8211; Unterteilung des Feldes in Partitionen<\/h3>\n<p>Der Drehpunkt befindet sich nach der Neuanordnung des Arrays an der richtigen Position und wird als klassifiziertes Element betrachtet. Au\u00dferdem wird das urspr\u00fcngliche Array in zwei Partitionen aufgeteilt, die wir rekursiv als zwei separate Arrays behandeln, die sortiert werden m\u00fcssen. Die Schritte 1 bis 3 werden der Reihe nach wiederholt. Die Rekursion endet, wenn nur noch ein einziges Element im Array \u00fcbrig ist. Das Ergebnis der Sortierung stellt dann die einzelnen Elemente aus allen Partitionen dar.<\/p>\n<figure id=\"attachment_4168\" aria-describedby=\"caption-attachment-4168\" style=\"width: 880px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4166 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/quick-sort-ilustracia-880-775.webp\" alt=\"Illustration des Quicksort-Algorithmus\" width=\"880\" height=\"775\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/quick-sort-ilustracia-880-775.webp 880w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/quick-sort-ilustracia-880-775-300x264.webp 300w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/quick-sort-ilustracia-880-775-768x676.webp 768w\" sizes=\"auto, (max-width: 880px) 100vw, 880px\" \/><figcaption id=\"caption-attachment-4168\" class=\"wp-caption-text\">Visuelle Darstellung des Quick-Sort-Algorithmus. Die gr\u00fcnen (und sp\u00e4ter roten) K\u00e4stchen zeigen die Auswahl des Pivots an.<\/figcaption><\/figure>\n<p>&nbsp;<\/p>\n<h2>Quick sort Animation, Visualisierung, gif<\/h2>\n<p>Die Quick sort Animation sieht so aus:<\/p>\n<figure id=\"attachment_4162\" aria-describedby=\"caption-attachment-4162\" style=\"width: 973px\" class=\"wp-caption alignnone\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4160 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/Quicksort.gif\" alt=\"Simpsons contributor, CC BY-SA 4.0, via Wikimedia Commons\" width=\"973\" height=\"271\" \/><figcaption id=\"caption-attachment-4162\" class=\"wp-caption-text\">Simpsons contributor, CC BY-SA 4.0, via Wikimedia Commons<\/figcaption><\/figure>\n<p>Quelle: commons.wikimedia.org\/wiki\/Category:Animations_of_sort_algorithms<\/p>\n<p>Eine Animation des Algorithmus findest du z.B. auf <a href=\"https:\/\/www.toptal.com\/developers\/sorting-algorithms\" target=\"_blank\" rel=\"nofollow noopener\">Toptal.<\/a> Es gibt 8 Arten von Algorithmen, du kannst die Animation auch r\u00fcckw\u00e4rts abspielen. Auf dieser <a href=\"https:\/\/www.hackerearth.com\/practice\/algorithms\/sorting\/quick-sort\/visualize\/\" target=\"_blank\" rel=\"nofollow noopener\">Seite<\/a> kannst du die Schritte des Algorithmus durchlaufen, so dass du den Zeitverbrauch des Algorithmus \u00fcberpr\u00fcfen kannst.<\/p>\n<h2>Vorteile des Quick Sort Algorithmus<\/h2>\n<ul>\n<li>Effizient f\u00fcr gro\u00dfe Zufallsdatens\u00e4tze,<\/li>\n<li>w\u00e4hrend der Sortierung werden keine Daten kopiert (In-place-Sortierung),<\/li>\n<li>kann parallelisiert werden und so die Rechenlast auf mehrere Prozessoren verteilen.<\/li>\n<\/ul>\n<h2>Nachteile des Quick Sort Algorithmus<\/h2>\n<ul>\n<li>Sie ist nicht stabil,<\/li>\n<li>Empfindlich gegen\u00fcber der Wahl des geeigneten Pivots,<\/li>\n<li>aufgrund des mit rekursiven Aufrufen und der Partitionsverwaltung verbundenen Overheads ungeeignet f\u00fcr kleine Datens\u00e4tze.<\/li>\n<\/ul>\n<h2>Quicksort \u2013 Zeitkomplexit\u00e4t<\/h2>\n<table width=\"536\">\n<thead>\n<tr>\n<th rowspan=\"2\" width=\"94\"><strong>Algorithmus<\/strong><\/th>\n<th rowspan=\"2\" width=\"84\"><strong>Methode<\/strong><\/th>\n<th colspan=\"3\" width=\"208\"><strong>Zeitliche Komplexit\u00e4t<\/strong><\/th>\n<th rowspan=\"2\" width=\"82\"><strong>Speicher<\/strong><\/th>\n<th rowspan=\"2\" width=\"69\"><strong>Stabil<\/strong><\/th>\n<\/tr>\n<tr>\n<th width=\"73\"><strong>schlechteste<\/strong><\/th>\n<th width=\"63\"><strong>durchschnittlich<\/strong><\/th>\n<th width=\"71\"><strong>beste<\/strong><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td width=\"94\">Quick sort<\/td>\n<td width=\"84\">Vertrieb<\/td>\n<td width=\"73\">O(n\u00b2)<\/td>\n<td width=\"63\">O(n log n)<\/td>\n<td width=\"71\">O(n log n)<\/td>\n<td width=\"82\">O(log n)<\/td>\n<td width=\"69\">Nein<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Quick Sort &#8211; Implementierung, Java-Code<\/h2>\n<p>Jetzt schauen wir uns die Implementierung des Quicksort-Algorithmus in Java an.<\/p>\n<p><strong><u>QuickSort.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">package sorting;\n\npublic class QuickSort {\n    public void sort(int[] data, int low, int high)\n    {\n        if (low &gt;= high)\n            return;\n        \/\/ Pivot index (pi)\n        int pi = partition(data, low, high);\n        \/\/ Sort both parts of array recursively\n        sort(data, low, pi - 1);\n        sort(data, pi + 1, high);\n    }\n    \n    private int partition(int[] data, int low, int high) {\n        \/\/ Selection of pivot (last element)\n        int pivot = data[high];\n        \/\/ Index of last element smaller than pivot\n        int i = (low - 1);\n        \/\/ Compare each element with pivot\n        for (int j = low; j &lt; high; j++) {\n            if (data[j] &lt;= pivot) {\n                \/\/ Swap the smaller element with greater placed on (i+1)\n                int temp = data[++i];\n                data[i] = data[j];\n                data[j] = temp;\n            }\n        }\n        \/\/ Swap of pivot\n        int temp = data[++i];\n        data[i] = data[high];\n        data[high] = temp;\n        \/\/ Print some algo information\n        System.out.println(&quot;Pivot selected: &quot; + data[i]);\n        printArray(data, low, i - 1);\n        System.out.print(&quot;(&quot; + data[i] + &quot;) &quot;);\n        printArray(data, i + 1, high);\n        System.out.println();\n        \/\/ Returns the pivot index\n        return i;\n    }\n\n    \/\/ Function to print an array\n    public void printArray(int[] data)\n    {\n        for (int i = 0; i &lt; data.length; i++)\n            System.out.print(data[i] + &quot; &quot;);\n    }\n    public void printArray(int[] data, int low, int high)\n    {\n        for (int i = low; i &lt;= high; i++)\n            System.out.print(data[i] + &quot; &quot;);\n    }\n}<\/code><\/pre>\n<p>&nbsp;<\/p>\n<p><strong><u>Main.java<\/u><\/strong><\/p>\n<pre><code class=\"language-java\" data-line=\"\">import sorting.QuickSort;\n\npublic class Main {\n    public static void main(String[] args) {\n        int[] dataToSort = { 9, 1, 8, 2, 7, 3, 5, 6, 4 };\n        QuickSort quickSort = new QuickSort();\n        System.out.print(&quot;Input: &quot;);\n        quickSort.printArray(dataToSort);\n        System.out.println();\n        quickSort.sort(dataToSort, 0, dataToSort.length - 1);\n        System.out.print(&quot;Sorted: &quot;);\n        quickSort.printArray(dataToSort);\n    }\n}<\/code><\/pre>\n<p>Die Ausgabe dieses Beispiels ist:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-4154 size-full\" src=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-quick-sort-440-525.webp\" alt=\"Quicksort Beispiel\" width=\"440\" height=\"525\" srcset=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-quick-sort-440-525.webp 440w, https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/vystup-z-prikladu-quick-sort-440-525-251x300.webp 251w\" sizes=\"auto, (max-width: 440px) 100vw, 440px\" \/><\/p>\n<p>Wir haben die Dateien mit dem obigen Beispiel in Form von Code vorbereitet, den du direkt in Java ausf\u00fchren kannst. Lade <a href=\"https:\/\/msgprogramator.sk\/wp-content\/uploads\/2024\/08\/QuickSort.zip\" target=\"_blank\" rel=\"noopener\">den Java <strong>QuickSort<\/strong> Code<\/a> hier herunter.<\/p>\n<p>Wenn du ein <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/java-entwickler-senior\/\" target=\"_blank\" rel=\"noopener\">Java Programmierer<\/a> bist und nach Arbeit suchst, schau dir unsere <a href=\"https:\/\/msg-life.sk\/de\/mitarbeiter-benefits\/\" target=\"_blank\" rel=\"noopener\">Mitareiterbenefits <\/a> an und reagiere auf die <a href=\"https:\/\/msg-life.sk\/de\/stellenangebote\/\" target=\"_blank\" rel=\"noopener\">neuesten Stellenangebote<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In diesem Artikel erf\u00e4hrst du, was Quick Sort ist, sein Prinzip, seine Vor- und Nachteile, seine Visualisierung und seinen Java-Beispielcode.<\/p>\n","protected":false},"author":14,"featured_media":4159,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[57],"tags":[],"class_list":["post-4827","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-java"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4827","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/comments?post=4827"}],"version-history":[{"count":5,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4827\/revisions"}],"predecessor-version":[{"id":9734,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/posts\/4827\/revisions\/9734"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media\/4159"}],"wp:attachment":[{"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/media?parent=4827"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/categories?post=4827"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/msgprogramator.sk\/de\/wp-json\/wp\/v2\/tags?post=4827"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}