Share
In diesem Abschnitt werden wir uns fünf Algorithmen ansehen, die zum Sortieren von Daten in einem Array verwendet werden. Wir beginnen mit einem naiven Algorithmus, der Blasensortierung, und enden mit dem gebräuchlichsten Allzweck-Sortieralgorithmus, der schnellen Sortierung.
Mit jedem Algorithmus werde ich erklären, wie die Sortierung durchgeführt wird, und auch Informationen zur besten, durchschnittlichen und Worst-Case-Komplexität für Leistung und Speicherauslastung geben.
Um den Code des Sortieralgorithmus etwas lesbarer zu halten, ist es üblich Wechsel Diese Methode wird von jedem Sortieralgorithmus verwendet, der Werte in einem Array nach Index austauschen muss.
void Swap (T [] Elemente, int links, int rechts) if (links! = rechts) T temp = items [links]; Artikel [links] = Artikel [rechts]; Artikel [rechts] = Temp;
| Verhalten | Sortiert das Eingabefeld mit dem Blasensortieralgorithmus. | ||
| Komplexität | I'm besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | Auf) | Auf2) | Auf2) |
| Platz | O (1) | O (1) | O (1) |
Die Blasensortierung ist ein naiver Sortieralgorithmus, der mehrere Durchläufe durch das Array durchführt, wobei jedes Mal der größte unsortierte Wert an das rechte Ende des Arrays verschoben wird.
Betrachten Sie das folgende unsortierte Array von Ganzzahlen:
Unsortiertes Array von Ganzzahlen Beim ersten Durchlauf durch das Array werden die Werte drei und sieben verglichen. Da sieben größer als drei sind, wird kein Swap durchgeführt. Als nächstes werden sieben und vier verglichen. Sieben ist größer als vier, also werden die Werte vertauscht, wodurch die Sieben einen Schritt näher an das Ende des Arrays gerückt werden. Das Array sieht nun so aus:
Die 4 und 7 haben Positionen getauscht Dieser Vorgang wird wiederholt und die sieben werden letztendlich mit den acht verglichen, was größer ist, so dass kein Swapping ausgeführt werden kann, und der Durchlauf endet am Ende des Arrays. Am Ende von Durchlauf 1 sieht das Array folgendermaßen aus:
Das Array am Ende von Durchlauf 1 Da mindestens ein Swap ausgeführt wurde, wird ein weiterer Durchlauf durchgeführt. Nach dem zweiten Durchgang haben sich die Sechs in Position bewegt.
Das Array am Ende von Durchlauf 2 Da mindestens ein Austausch durchgeführt wurde, wird erneut ein Durchlauf durchgeführt.
Der nächste Durchgang stellt jedoch fest, dass keine Swaps erforderlich waren, da sich alle Elemente in der Sortierreihenfolge befinden. Da keine Auslagerungen durchgeführt wurden, ist bekannt, dass das Array sortiert ist und der Sortieralgorithmus abgeschlossen ist.
public void Sort (T [] Elemente) bool getauscht; do swapped = false; für (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Swap (Elemente, i - 1, i); vertauscht = wahr; while (getauscht! = falsch);
| Verhalten | Sortiert das Eingabearray mit dem Einfügungssortieralgorithmus. | ||
| Komplexität | I'm besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | Auf) | Auf2) | Auf2) |
| Platz | O (1) | O (1) | O (1) |
Die Einfügungssortierung funktioniert, indem Sie das Array einmal durchlaufen und den aktuellen Wert in den bereits sortierten (Anfangs-) Teil des Arrays einfügen. Nachdem jeder Index bearbeitet wurde, ist bekannt, dass alles, was bisher gefunden wurde, sortiert wird und alles, was folgt, unbekannt ist.
Warte was?
Das wichtige Konzept besteht darin, dass die Einfügungssortierung funktioniert, indem Elemente bei ihrem Auftreten sortiert werden. Da das Array von links nach rechts verarbeitet wird, wissen wir, dass alles links vom aktuellen Index sortiert ist. Diese Grafik zeigt, wie das Array bei jedem Index sortiert wird:
Ein Array, das durch Einfügungssortierung verarbeitet wird Während die Verarbeitung fortgesetzt wird, wird das Array immer mehr sortiert, bis es vollständig sortiert ist.
Schauen wir uns ein konkretes Beispiel an. Das folgende ist ein unsortiertes Array, das mittels Einfügungssortierung sortiert wird.
Unsortiertes Array von Ganzzahlen Wenn der Sortiervorgang beginnt, beginnt der Sortieralgorithmus bei Index Null mit dem Wert drei. Da diesem keine Werte vorausgehen, ist bekannt, dass das Array bis einschließlich Index Null sortiert ist.
Der Algorithmus geht dann auf den Wert sieben über. Da sieben größer ist als alles im bekannten sortierten Bereich (der derzeit nur drei umfasst), ist bekannt, dass die Werte bis einschließlich sieben in der Sortierreihenfolge liegen.
An diesem Punkt ist bekannt, dass die Feldindizes 0-1 sortiert sind und 2-n sich in einem unbekannten Zustand befinden.
Als nächstes wird der Wert bei Index zwei (vier) geprüft. Da vier weniger als sieben ist, ist es bekannt, dass vier an den richtigen Ort im sortierten Arraybereich verschoben werden müssen. Die Frage ist nun, zu welchem Index im sortierten Array der Wert eingefügt werden soll. Die Methode dazu ist die FindInsertionIndex im Codebeispiel gezeigt. Diese Methode vergleicht den einzufügenden Wert (vier) mit den Werten im sortierten Bereich, beginnend bei Index Null, bis der Punkt gefunden ist, an dem der Wert eingefügt werden soll.
Diese Methode bestimmt, dass Index Eins (zwischen drei und sieben) die geeignete Einfügemarke ist. Der Einfügungsalgorithmus (der Einfügen method) führt dann die Einfügung aus, indem der einzufügende Wert aus dem Array entfernt und alle Werte von der Einfügemarke zum entfernten Element nach rechts verschoben werden. Das Array sieht nun so aus:
Array nach dem ersten Einfügungsalgorithmus Es ist jetzt bekannt, dass das Array vom Index null bis zwei sortiert ist, und alles vom Index drei bis zum Ende ist unbekannt. Der Prozess beginnt nun wieder bei Index drei, der den Wert vier hat. Während der Algorithmus fortfährt, werden die folgenden Einfügungen vorgenommen, bis das Array sortiert ist.
Array nach weiteren Einfügungsalgorithmen Wenn keine weiteren Einfügungen mehr vorgenommen werden müssen oder wenn der sortierte Teil des Arrays das gesamte Array ist, ist der Algorithmus beendet.
Accentsconagua
public void Sort (T [] Elemente) int sortiertesRangeEndIndex = 1; while (sortiertRangeEndIndex < items.Length) if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0) int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]); Insert(items, insertIndex, sortedRangeEndIndex); sortedRangeEndIndex++; private int FindInsertionIndex(T[] items, T valueToInsert) for (int index = 0; index < items.Length; index++) if (items[index].CompareTo(valueToInsert) > 0) Rückkehrindex; werfen neue InvalidOperationException ("Der Einfügungsindex wurde nicht gefunden"); private void Insert (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // aktionen // 1: speichere den Index in in temp temp = 4 // 2: Index auf at setzen von -> 0 1 2 3 5 6 3 7 temp = 4 // 3: Rückschritt von Index zu Index bei + 1. // Werte von links nach rechts verschieben Einmal. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Schreibt den Temp-Wert bei + 1 in den Index. // 0 1 2 3 4 5 6 7 temp = 4 // Schritt 1. T temp = itemArray [indexInsertingAt]; // Schritt 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Schritt 3. für (int current = indexInsertingFrom; current> indexInsertingAt; current--) itemArray [current] = itemArray [current - 1]; // Schritt 4. itemArray [indexInsertingAt + 1] = temp; | Verhalten | Sortiert das Eingabearray mit dem Auswahlsortieralgorithmus. | ||
| Komplexität | I'm besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | Auf) | Auf2) | Auf2) |
| Platz | O (1) | O (1) | O (1) |
Auswahlsortierung ist eine Art Hybrid zwischen Blasensortierung und Einfügungssortierung. Wie bei der Bubble-Sortierung verarbeitet es das Array, indem es immer wieder vom Anfang bis zum Ende iteriert, einen Wert auswählt und an die richtige Stelle verschiebt. Im Gegensatz zur Bubblesortierung wird jedoch der kleinste unsortierte Wert und nicht der größte ausgewählt. Wie bei der Einfügungssortierung ist der sortierte Teil des Arrays der Anfang des Arrays, während bei Blasensortierung der sortierte Teil am Ende liegt.
Mal sehen, wie das mit dem gleichen unsortierten Array funktioniert, das wir verwendet haben.
Unsortiertes Array von Ganzzahlen Beim ersten Durchlauf versucht der Algorithmus, den kleinsten Wert im Array zu finden und im ersten Index zu platzieren. Dies wird von der durchgeführt FindIndexOfSmallestFromIndex, welcher den Index des kleinsten unsortierten Werts ab dem angegebenen Index findet.
Bei einem so kleinen Array können wir feststellen, dass der erste Wert drei der kleinste Wert ist, also bereits an der richtigen Stelle ist. An diesem Punkt wissen wir, dass der Wert in Arrayindex Null der kleinste Wert ist und daher in der richtigen Sortierreihenfolge vorliegt. Nun können wir also zwei übergeben - diesmal nur die Array-Einträge eins bis n-1.
Der zweite Durchlauf bestimmt, dass vier der kleinste Wert im unsortierten Bereich ist, und tauscht den Wert im zweiten Slot mit dem Wert in dem Slot, in dem vier gehalten wurde (Swap der vier und sieben). Nach Durchlaufen von zwei Abschlüssen wird der Wert vier an seiner sortierten Position eingefügt.
Array nach dem zweiten Durchlauf Der sortierte Bereich reicht jetzt von Index Null bis Index Eins, und der unsortierte Bereich reicht von Index Zwei bis N-1. Wenn jeder nachfolgende Durchgang abgeschlossen ist, wird der sortierte Abschnitt des Arrays größer und der unsortierte Abschnitt wird kleiner. Wenn an irgendeiner Stelle auf dem Weg keine Einfügungen vorgenommen werden, ist bekannt, dass das Array sortiert ist. Andernfalls wird der Prozess fortgesetzt, bis bekannt ist, dass das gesamte Array sortiert ist.
Nach zwei weiteren Durchläufen ist das Array sortiert:
Sortiertes Array public void Sort (T [] Elemente) int sortierteRangeEnd = 0; while (sortiertRangeEnd < items.Length) int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd) T currentSmallest = items[sortedRangeEnd]; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) if (currentSmallest.CompareTo(items[i]) > 0) currentSmallest = Elemente [i]; currentSmallestIndex = i; return currentSmallestIndex;
| Verhalten | Sortiert das Eingabearray mit dem Merge-Sortieralgorithmus. | ||
| Komplexität | I'm besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O (n log n) | O (n log n) | O (n log n) |
| Platz | Auf) | Auf) | Auf) |
Bisher haben wir Algorithmen gesehen, die durch lineare Verarbeitung des Arrays arbeiten. Diese Algorithmen haben den Vorteil, dass sie mit sehr wenig Speicheraufwand arbeiten, jedoch auf Kosten der quadratischen Laufzeitkomplexität. Mit der Merge-Sortierung sehen wir unseren ersten Algorithmus zum Teilen und Erobern.
Teilungs- und Eroberungsalgorithmen arbeiten, indem sie große Probleme in kleinere, leichter lösbare Probleme zerlegen. Wir sehen solche Algorithmen im Alltag. Zum Beispiel verwenden wir beim Durchsuchen eines Telefonbuchs einen Divide-and-Conquer-Algorithmus.
Wenn Sie den Namen Erin Johnson in einem Telefonbuch finden möchten, beginnen Sie nicht bei A und blättern Sie Seite für Seite vor. Vielmehr würden Sie das Telefonbuch wahrscheinlich in der Mitte öffnen. Wenn Sie sich für die Ms öffnen, blättern Sie ein paar Seiten zurück, vielleicht ein bisschen zu weit - die Hs vielleicht. Dann würden Sie nach vorne blättern. Und Sie würden in immer kleineren Schritten hin und her blättern, bis Sie schließlich die gewünschte Seite gefunden haben (oder so nahe waren, dass das Blättern nach vorne Sinn machte)..
Wie effizient sind Algorithmen zum Teilen und Erobern?
Angenommen, das Telefonbuch ist 1000 Seiten lang. Wenn Sie sich in der Mitte öffnen, haben Sie das Problem in zwei 500-Seiten-Probleme aufgeteilt. Vorausgesetzt, Sie befinden sich nicht auf der rechten Seite, können Sie jetzt die entsprechende Seite auswählen, um das Problem erneut zu halbieren. Jetzt ist dein Problemraum 250 Seiten. Da sich das Problem immer weiter halbiert, können wir feststellen, dass ein Telefonbuch mit 1000 Seiten in nur zehn Seitenumläufen durchsucht werden kann. Dies ist 1% der Gesamtanzahl von Seitenumläufen, die bei einer linearen Suche erforderlich sein könnten.
Bei der Zusammenführungssortierung wird das Array immer wieder halbiert, bis jedes Stück nur ein Element lang ist. Diese Elemente werden dann in der Sortierreihenfolge wieder zusammengefügt.
Beginnen wir mit dem folgenden Array:
Unsortiertes Array von Ganzzahlen Und jetzt schneiden wir das Array in zwei Hälften:
Unsortiertes Array halbiert Jetzt werden beide Arrays wiederholt halbiert, bis jedes Element für sich alleine ist:
Unsortiertes Array wird halbiert, bis jeder Index für sich alleine ist Wenn das Array nun in die kleinstmöglichen Teile aufgeteilt ist, erfolgt der Vorgang des Zusammenführens dieser Teile in Sortierreihenfolge.
Array in zwei Gruppen sortiert Die einzelnen Elemente werden zu sortierten Zweiergruppen, diese Zweiergruppen werden zu sortierten Vierergruppen zusammengeführt, und schließlich verschmelzen sie schließlich zu einem endgültigen sortierten Array.
Array in vier Gruppen (oben) und die vollständige Sortierung (unten) sortiert Nehmen wir uns einen Moment Zeit, um über die einzelnen Operationen nachzudenken, die wir implementieren müssen:
Sortieren Methode tut dies.Verschmelzen Methode tut dies.Ein Leistungsaspekt bei der Zusammenführungssortierung besteht darin, dass die Zusammenführungssortierung im Gegensatz zu den linearen Sortieralgorithmen ihre gesamte Split- und Zusammenführungslogik einschließlich der Speicherzuordnungen durchführt, selbst wenn das Array bereits in sortierter Reihenfolge ist. Im schlechtesten Fall ist die Leistung zwar besser als bei den linearen Sortieralgorithmen, jedoch ist der beste Fall immer schlechter. Das heißt, es ist kein idealer Kandidat beim Sortieren von Daten, von denen bekannt ist, dass sie nahezu sortiert sind. Zum Beispiel beim Einfügen von Daten in ein bereits sortiertes Array.
public void Sort (T [] Elemente) if (items.Length <= 1) return; int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T[] left = new T[leftSize]; T[] right = new T[rightSize]; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); private void Merge(T[] items, T[] left, T[] right) int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) if (leftIndex> = left.Length) items [targetIndex] = right [rightIndex ++]; else if (rightIndex> = right.Length) items [targetIndex] = left [leftIndex ++]; else if (left [leftIndex] .CompareTo (rechts [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Verhalten | Sortiert das Eingabearray mit dem schnellen Sortieralgorithmus. | ||
| Komplexität | I'm besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O (n log n) | O (n log n) | Auf2) |
| Platz | O (1) | O (1) | O (1) |
Schnelle Sortierung ist ein weiterer Algorithmus zum Teilen und Erobern. Dies geschieht, indem der folgende Algorithmus rekursiv ausgeführt wird:
Lassen Sie uns das folgende Array schnell sortieren:
Unsortiertes Array von Ganzzahlen Schritt eins sagt, dass wir den Partitionspunkt mit einem zufälligen Index auswählen. Im Beispielcode geschieht dies in dieser Zeile:
int pivotIndex = _pivotRng.Next (links, rechts);
Einen zufälligen Partitionsindex auswählen Nun, da wir den Partitionsindex kennen (vier), betrachten wir den Wert an diesem Punkt (sechs) und verschieben die Werte im Array, sodass sich alles unterhalb des Werts auf der linken Seite des Arrays befindet und alles andere (Werte größer) als oder gleich) wird auf die rechte Seite des Arrays verschoben. Beachten Sie, dass das Verschieben der Werte den Index ändern kann, in dem der Partitionswert gespeichert ist (wir werden das in Kürze sehen)..
Das Austauschen der Werte erfolgt durch die Partitionsmethode im Beispielcode.
Werte nach links und rechts vom Partitionswert verschieben An diesem Punkt wissen wir, dass sich sechs im Array an der richtigen Stelle befinden. Wir wissen das, weil jeder Wert links kleiner als der Partitionswert ist und alles rechts davon größer oder gleich dem Partitionswert ist. Jetzt wiederholen wir diesen Vorgang auf den zwei unsortierten Partitionen des Arrays.
Die Wiederholung erfolgt im Beispielcode durch rekursives Aufrufen der Quicksort-Methode mit jeder der Array-Partitionen. Beachten Sie, dass diesmal das linke Array bei Index eins mit dem Wert fünf partitioniert ist. Durch das Verschieben der Werte an die entsprechenden Positionen wird der Wert fünf in einen anderen Index verschoben. Ich weise darauf hin, um den Punkt zu unterstreichen, dass Sie einen Partitionswert auswählen, nicht einen Partitionsindex.
Drehpunkt und Partition wiederholen Schnell wieder sortieren:
Drehpunkt und Partition noch einmal wiederholen Und noch ein letztes Mal schnell sortiert:
Drehpunkt und Partition noch einmal wiederholen Da nur noch ein unsortierter Wert übrig ist und wir wissen, dass jeder andere Wert sortiert ist, ist das Array vollständig sortiert.
Random _pivotRng = new Random (); public void Sort (T [] items) quicksort (items, 0, items.Length - 1); private void quicksort (T [] Elemente, int left, int right) if (links) < right) int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); private int partition(T[] items, int left, int right, int pivotIndex) T pivotValue = items[pivotIndex]; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) if (items[i].CompareTo(pivotValue) < 0) Swap(items, i, storeIndex); storeIndex += 1; Swap(items, storeIndex, right); return storeIndex;
