{"id":193139,"date":"2026-02-19T12:55:01","date_gmt":"2026-02-19T11:55:01","guid":{"rendered":"https:\/\/liora.io\/de\/?p=193139"},"modified":"2026-02-19T12:55:02","modified_gmt":"2026-02-19T11:55:02","slug":"quicksort-beschreibung-und-bedeutung-dieses-sortieralgorithmus","status":"publish","type":"post","link":"https:\/\/liora.io\/de\/quicksort-beschreibung-und-bedeutung-dieses-sortieralgorithmus","title":{"rendered":"QUICKSORT: Beschreibung und Bedeutung dieses Sortieralgorithmus"},"content":{"rendered":"

Quicksort ist einer der besten Sortieralgorithmen, der bei gro\u00dfen Datenstrukturen wie Listen und Tabellen eingesetzt wird. Im Folgenden erf\u00e4hrst du, wie dieser Algorithmus funktioniert, welche verschiedenen Anwendungsf\u00e4lle es gibt und wie leistungsf\u00e4hig er ist.<\/strong><\/p>\t\t\n\t\t

Die Schnellsortierung oder Pivot-Sortierung<\/strong> ist ein Sortieralgorithmus, der 1961 von Tony Hoare erfunden wurde, als er als Gaststudent an der Moskauer Staatsuniversit\u00e4t studierte.<\/p>

Zu den bekanntesten und am h\u00e4ufigsten verwendeten Sortieralgorithmen der Welt geh\u00f6rt auch die Quicksort. Quicksort ist eine Sortiertechnik, die verwendet wird, um die Elemente einer Datenstruktur in einer bestimmten Reihenfolge (aufsteigend oder absteigend) anzuordnen. Sie wird in der Regel bei Tabellen verwendet, kann aber auch bei Listen eingesetzt werden. Dieser Sortieralgorithmus basiert haupts\u00e4chlich auf dem DPR-Ansatz (Dividieren und Herrschen)<\/strong>, bei dem zwei oder mehr Arrays mit einer Gr\u00f6\u00dfe, die strikt kleiner als n ist, verwendet werden, um ein Sortierproblem f\u00fcr ein Array der Gr\u00f6\u00dfe n zu l\u00f6sen.<\/p>

Bei der Schnellsortierung wird von Anfang an ein Element des zu sortierenden Arrays ausgew\u00e4hlt, das als Pivot bezeichnet wird, manchmal zuf\u00e4llig oder auf bestimmte Weise (normalerweise das erste Element oder das letzte Element des Eingabe-Arrays).<\/p>

Anschlie\u00dfend muss die Eingabetabelle um den Pivot herum partitioniert werden, indem der Pivot an seiner entsprechenden Position in der sortierten Tabelle, d. h. seiner endg\u00fcltigen Position, platziert wird: Dies wird durch eine Partitionierungsfunktion gew\u00e4hrleistet.<\/p>

Der Partitionierungsalgorithmus<\/strong> ist ein iterativer Algorithmus,<\/a> der die gesamte zu sortierende Tabelle durchl\u00e4uft, um alle Elemente, die kleiner als der Pivot sind, links von diesem zu platzieren und alle Elemente, die gr\u00f6\u00dfer als der Pivot sind, rechts von diesem zu platzieren.<\/p>\t\t\n\t\t\t\n

Alles \u00fcber den Quicksort-Algorithmus<\/a><\/div><\/div>\n\n\t\t\t

Alles \u00fcber den Quicksort-Algorithmus<\/h2>\t\t\n\t\t

Die Partitionierungsfunktion<\/strong> durchl\u00e4uft iterativ die zu sortierende Tabelle, um die einzelnen Elemente mit dem Pivot zu vergleichen. Wenn ein Element gefunden wird, das kleiner als der Pivot ist, wird die Position dieses Elements mit dem Wert eines gr\u00f6\u00dferen Elements, das vor ihm in der Liste auftaucht, ge\u00e4ndert. Wenn man auf ein Element st\u00f6\u00dft, das gr\u00f6\u00dfer als die Pivotlinie ist, tut man nichts.<\/p>

Als Ergebnis der Partition<\/strong> erh\u00e4lt man den Index des Pivots in der sortierten Tabelle, der somit sein endg\u00fcltiger Index ist, und man tauscht somit die Anfangs- und Endposition des Pivots aus.<\/p>

Die Wahl des Pivots ist entscheidend, da die Partitionierung der Datenstruktur um den Pivot herum durchgef\u00fchrt wird. Wenn der Pivot die Tabelle nicht in zwei ann\u00e4hernd gleich gro\u00dfe Untertabellen aufteilt, d.h. wenn der Pivot nicht mehr oder weniger dem Median entspricht, sondern einem Grenzwert der zu sortierenden Menge, wird die Partitionierung eine leere Menge der Gr\u00f6\u00dfe und eine Menge der Gr\u00f6\u00dfe n-1 ergeben, wenn die Anfangsgr\u00f6\u00dfe n war.<\/p>

Im ersten Schritt erfordert diese Aufteilung n Operationen. Im n\u00e4chsten Zug erfordert sie n-1, dann n-2, bis nichts mehr zum Sortieren \u00fcbrig ist, was genau dem Prinzip der Auswahlsortierung entspricht, die eine quadratische Komplexit\u00e4t hat.<\/p>

Eine allgemein akzeptierte Idee ist es, den Median von drei zuf\u00e4lligen Werten aus der Tabelle als Pivot zu nehmen, um die Situation der Wahl des falschen Pivots zu vermeiden.<\/strong><\/p>\t\t\n\t\t\t

Was ist zu tun, nachdem du die Endposition des Pivots nach der Partitionierungsfunktion erhalten hast?<\/h3>\t\t\n\t\t

Nachdem du die Endposition des Pivots<\/strong> erhalten und die Indizes ausgetauscht hast, musst du die Schnellsortierfunktion auf die beiden Untertabellen anwenden, die du auf beiden Seiten des Pivots erhalten hast.<\/p>

Das hei\u00dft, die linke Untertabelle, die durch Array[Start,Pivot(Index)-1] markiert ist, und die rechte Untertabelle, die durch Array [Pivot(Index)+1,Ende] markiert ist, wobei Pivot(Index) dem Pivot-Index entspricht, den du nach der Partitionierungsfunktion f\u00fcr die Eingangstabelle erhalten hast.<\/p>

Als N\u00e4chstes m\u00fcssen wir zwei Pivots ausw\u00e4hlen, die den Pivots der linken und rechten Untertabelle entsprechen, und dann einen rekursiven Aufruf der Funktion zum schnellen Sortieren auf diese beiden Untertabellen anwenden. Die rekursiven Aufrufe der Quicksort-Funktion<\/strong> werden entweder beendet, wenn der Start- und der Endindex eines Unterarrays gleich sind, was bedeutet, dass das Array nur ein Element enth\u00e4lt und somit bereits sortiert ist, oder wenn der Startindex eines Unterarrays gr\u00f6\u00dfer ist als sein Endindex, was bedeutet, dass das Array kein Element enth\u00e4lt (leeres Array) und somit ebenfalls sortiert ist.<\/p>\t\t\n\t\t\t\n

Alles \u00fcber den Quicksort-Algorithmus lernen<\/a><\/div><\/div>\n\n\t\t\t

Illustration der Schnellsortierung \/ Quicksort<\/h3>\t\t\n\t\t

Betrachte zur Veranschaulichung das folgende Array, bei dem der Pivot als das am weitesten rechts stehende Element gew\u00e4hlt wurde, d. h. array[length(array)-1] = 4:<\/p>

array = [9, 12, 1, 5, 6, 13, 8, 2, 4]<\/pre>
\n\t\t\t\t\t\t\t\t\t\t\"\"\t\t\t\t\t\t\t\t\t\t\t
<\/figcaption>\n\t\t\t\t\t\t\t\t\t\t<\/figure>\n\t\t