Einführung
Das Sortieren eines Arrays ist eines der ersten ernsthaften Probleme, die im klassischen Kurs "Algorithmen und Datenstrukturen" der Informatikdisziplin untersucht wurden. In diesem Zusammenhang werden die Aufgaben des Schreibensortierens und die entsprechenden Fragen häufig in Interviews für die Position eines Praktikanten oder Nachwuchsentwicklers angetroffen.
Formulierung des Problems
Traditionell lohnt es sich, die Präsentation von Lösungen für das Problem mit seiner Aussage zu beginnen. Normalerweise besteht die Sortieraufgabe darin, ein Array von Ganzzahlen in aufsteigender Reihenfolge zu ordnen. Tatsächlich ist dies jedoch etwas zu einfach. Die in diesem Abschnitt beschriebenen Algorithmen können verwendet werden, um ein Array von Objekten zu ordnen, zwischen denen eine Ordnungsbeziehung hergestellt wird (dh für zwei beliebige Elemente können wir sagen: Das erste ist größer als das zweite, das zweite ist größer als das erste oder sie sind gleich). Sie können sowohl in aufsteigender als auch in absteigender Reihenfolge sortieren. Wir werden die Standardvereinfachung verwenden.
Schnelle Sorte
Das letzte Mal haben wir über eine etwas komplexere Sortierung gesprochen - die Einfügungssortierung. Heute werden wir über einen viel komplexeren Algorithmus sprechen - die schnelle Sortierung (auch Hoare-Sortierung genannt).
Algorithmusbeschreibung
Der schnelle Sortieralgorithmus ist rekursiv, daher nimmt die Prozedur der Einfachheit halber die Grenzen eines Arraysegments von l einschließlich bis r nicht inklusive als Eingabe. Es ist klar, dass Sie zum Sortieren des gesamten Arrays 0 als Parameter l und n als r übergeben müssen, wobei n traditionell die Länge des Arrays bezeichnet.
Der Quicksort-Algorithmus basiert auf der Partitionsprozedur. Die Partition wählt ein Element des Arrays aus und ordnet die Elemente des Arrays so neu, dass das Array in zwei Teile aufgeteilt wird: Die linke Seite enthält Elemente, die kleiner als dieses Element sind, und die rechte Seite enthält Elemente, die größer oder gleich diesem Element sind. Dieses Trennelement wird als Drehpunkt bezeichnet .
Partiion Implementierung:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
Der Drehpunkt wird in unserem Fall zufällig ausgewählt. Dieser Algorithmus wird als randomisiert bezeichnet . Tatsächlich kann der Pivot auf verschiedene Arten ausgewählt werden: entweder ein zufälliges Element oder das erste / letzte Element des Abschnitts oder eine „intelligente“ Auswahl. Die Wahl des Pivots ist sehr wichtig für die endgültige Komplexität des Sortieralgorithmus, aber dazu später mehr. Die Komplexität der Partitionsprozedur ist O (n), wobei n = r - l die Länge des Abschnitts ist.
Jetzt verwenden wir die Partition, um die Sortierung zu implementieren:
Partitionsimplementierung:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
Ein Extremfall - ein Array aus einem Element hat die Eigenschaft, geordnet zu werden. Wenn das Array lang ist, verwenden wir die Partition und rufen die Prozedur rekursiv für die beiden Hälften des Arrays auf.
Wenn Sie die schriftliche Sortierung am Beispiel des Arrays 1 2 2 ausführen, werden Sie feststellen, dass sie niemals enden wird. Warum ist das passiert?
Beim Schreiben der Partition haben wir angenommen, dass alle Elemente des Arrays eindeutig sein müssen. Andernfalls ist der Rückgabewert von m l und die Rekursion wird niemals enden, da sort (l, m) sort (l, l) und sort (l, m) aufruft. Um dieses Problem zu lösen, müssen Sie das Array nicht in zwei Teile (<Pivot und> = Pivot), sondern in drei Teile (<Pivot, = Pivot,> Pivot) unterteilen und die rekursive Sortierung für den 1. und 3. Teil aufrufen.
Analyse
Ich schlage vor, diesen Algorithmus zu analysieren.
Die zeitliche Komplexität des Algorithmus wird dadurch durch die Formel ausgedrückt: T (n) = n + T (a * n) + T ((1 - a) * n). Wenn wir also die Sortierung eines Arrays von n Elementen aufrufen, dauert es ungefähr n Operationen, um die Partition auszuführen und sich selbst zweimal mit den Parametern a * n und (1 - a) * n auszuführen, da der Pivot das Element in Brüche unterteilt hat.
Im besten Fall ist a = 1/2, dh der Drehpunkt teilt die Fläche jedes Mal in zwei gleiche Teile. In diesem Fall gilt: T (n) = n + 2 · T (n / 2) = n + 2 · (n / 2 + 2 · T (n / 4)) = n + n + 4 · T (n / 4) ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. Insgesamt sind log (n) Terme, da die Terme erscheinen, bis das Argument auf 1 abfällt. Als Ergebnis ist T (n) = O (n * log (n)).
Im schlimmsten Fall ist a = 1 / n, dh der Drehpunkt schneidet genau ein Element ab. Der erste Teil des Arrays enthält 1 Element und der zweite Teil enthält n - 1. Das heißt: T (n) = n + T (1) + T (n - 1) = n + O (1) + T (n - 1) = n + O (1) + (n - 1 + O (1) + T (n - 2)) = O (n ^ 2). Das Quadrat erscheint aufgrund der Tatsache, dass es in der Formel für die Summe einer arithmetischen Folge erscheint, die beim Kritzeln der Formel auftritt.
Im Idealfall sollte im Durchschnitt die mathematische Erwartung verschiedener Optionen berücksichtigt werden. Es kann gezeigt werden, dass, wenn der Pivot das Array im Verhältnis 1: 9 teilt, die resultierende Asymptotik immer noch O (n * log (n)) ist.
Das Sortieren wird als schnell bezeichnet, da sich die unter dem O-Zeichen verborgene Konstante in der Praxis als recht klein herausstellt, was in der Praxis zu einer weit verbreiteten Verwendung des Algorithmus führte.
Weiterlesen
