German (Deutsch) translation by Tatsiana Bochkareva (you can also view the original English article)
In diesem Abschnitt werden fünf Algorithmen vorgestellt, mit denen Daten in einem Array sortiert werden. Wir beginnen mit einem naiven Algorithmus, der Blasensortierung, und enden mit dem gängigsten allgemeinen Sortieralgorithmus, der schnellen Sortierung.
Mit jedem Algorithmus werde ich erklären, wie die Sortierung durchgeführt wird, und Informationen zur besten, durchschnittlichen und schlechtesten Komplexität sowohl für die Leistung als auch für die Speichernutzung bereitstellen.
Swap
Um den Code des Sortieralgorithmus ein wenig leichter lesbar zu halten, wird von jedem Sortieralgorithmus, der Werte in einem Array nach Index austauschen muss, eine übliche Swap-Methode verwendet.
1 |
void Swap(T[] items, int left, int right) |
2 |
{
|
3 |
if (left != right) |
4 |
{
|
5 |
T temp = items[left]; |
6 |
items[left] = items[right]; |
7 |
items[right] = temp; |
8 |
}
|
9 |
}
|
Bubble sortierung
| Verhalten | Sortiert das Eingabearray mithilfe des Blasensortierungsalgorithmus. | ||
| Komplexität | Besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O(n) | O(n2) | O(n2) |
| Raum | O(1) | O(1) | O(1) |
Die Blasensortierung ist ein naiver Sortieralgorithmus, der mehrere Durchgänge durch das Array durchführt und jedes Mal den größten unsortierten Wert nach rechts (Ende) des Arrays verschiebt.
Betrachten Sie das folgende unsortierte Array von Ganzzahlen:
Beim ersten Durchlauf durch das Array werden die Werte drei und sieben verglichen. Da sieben größer als drei ist, wird kein Tausch durchgeführt. Als nächstes werden sieben und vier verglichen. Sieben ist größer als vier, daher werden die Werte vertauscht, wodurch die Sieben einen Schritt näher an das Ende des Arrays gerückt werden. Das Array sieht jetzt so aus:
Dieser Vorgang wird wiederholt, und die sieben werden schließlich mit den acht verglichen, was größer ist, so dass kein Austausch durchgeführt werden kann, und der Durchlauf endet am Ende des Arrays. Am Ende des ersten Durchgangs sieht das Array folgendermaßen aus:
Da mindestens ein Tausch durchgeführt wurde, wird ein weiterer Durchgang durchgeführt. Nach dem zweiten Durchgang haben sich die sechs in Position bewegt.
Da mindestens ein Swap durchgeführt wurde, wird erneut ein Durchlauf durchgeführt.
Der nächste Durchgang stellt jedoch fest, dass keine Swaps erforderlich waren, da alle Artikel in Sortierreihenfolge sind. Da keine Swaps durchgeführt wurden, ist bekannt, dass das Array sortiert ist und der Sortieralgorithmus vollständig ist.
1 |
public void Sort(T[] items) |
2 |
{
|
3 |
bool swapped; |
4 |
|
5 |
do
|
6 |
{
|
7 |
swapped = false; |
8 |
for (int i = 1; i < items.Length; i++) |
9 |
{
|
10 |
if (items[i - 1].CompareTo(items[i]) > 0) |
11 |
{
|
12 |
Swap(items, i - 1, i); |
13 |
swapped = true; |
14 |
}
|
15 |
}
|
16 |
} while (swapped != false); |
17 |
}
|
Sortieren durch Einfügen
| Verhalten | Sortiert das Eingabearray mithilfe des Einfügesortieralgorithmus. | ||
| Komplexität | Besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O(n) | O(n2) | O(n2) |
| Raum | O(1) | O(1) | O(1) |
Die Einfügesortierung funktioniert, indem ein einzelner Durchgang durch das Array durchgeführt und der aktuelle Wert in den bereits sortierten (Anfangs-) Teil des Arrays eingefügt wird. Nachdem jeder Index verarbeitet wurde, ist bekannt, dass alles, was bisher angetroffen wurde, sortiert ist und alles, was folgt, unbekannt ist.
Warten Sie, was weiter ist?
Das wichtige Konzept besteht darin, dass die Einfügesortierung funktioniert, indem Elemente so sortiert werden, wie sie angetroffen 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 sortiert wird, wenn jeder Index angetroffen 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 mithilfe der Einfügesortierung sortiert wird.
Wenn der Sortiervorgang beginnt, beginnt der Sortieralgorithmus bei Index Null mit dem Wert Drei. Da dem keine Werte vorausgehen, ist bekannt, dass das Array bis einschließlich Index Null sortiert ist.
Der Algorithmus fährt dann mit dem Wert sieben fort. Da sieben größer ist als alles in dem bekannten sortierten Bereich (der derzeit nur drei enthält), sind die Werte bis einschließlich sieben bekanntermaßen in Sortierreihenfolge.
Zu diesem Zeitpunkt ist bekannt, dass die Array-Indizes 0-1 sortiert sind, und 2-n befindet sich in einem unbekannten Zustand.
Der Wert am Index zwei (vier) wird als nächstes überprüft. Da vier kleiner als sieben ist, ist bekannt, dass vier an die richtige Stelle im sortierten Array-Bereich verschoben werden müssen. Die Frage ist nun, in welchen Index im sortierten Array der Wert eingefügt werden soll. Die Methode hierfür ist der im Codebeispiel gezeigte FindInsertionIndex. Diese Methode vergleicht den einzufügenden Wert (vier) mit den Werten im sortierten Bereich, beginnend mit dem 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ügealgorithmus (die Insert methode) führt dann die Einfügung durch, 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 jetzt so aus:
Es ist jetzt bekannt, dass das Array von Index Null bis Zwei sortiert ist, und alles von Index Drei bis zum Ende ist unbekannt. Der Prozess beginnt nun erneut bei Index drei, der den Wert vier hat. Im weiteren Verlauf des Algorithmus werden die folgenden Einfügungen ausgeführt, bis das Array sortiert ist.
Wenn keine weiteren Einfügungen durchgeführt werden müssen oder wenn der sortierte Teil des Arrays das gesamte Array ist, ist der Algorithmus beendet.
1 |
public void Sort(T[] items) |
2 |
{
|
3 |
int sortedRangeEndIndex = 1; |
4 |
|
5 |
while (sortedRangeEndIndex < items.Length) |
6 |
{
|
7 |
if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0) |
8 |
{
|
9 |
int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]); |
10 |
Insert(items, insertIndex, sortedRangeEndIndex); |
11 |
}
|
12 |
|
13 |
sortedRangeEndIndex++; |
14 |
}
|
15 |
}
|
16 |
|
17 |
private int FindInsertionIndex(T[] items, T valueToInsert) |
18 |
{
|
19 |
for (int index = 0; index < items.Length; index++) |
20 |
{
|
21 |
if (items[index].CompareTo(valueToInsert) > 0) |
22 |
{
|
23 |
return index; |
24 |
}
|
25 |
}
|
26 |
|
27 |
throw new InvalidOperationException("The insertion index was not found"); |
28 |
}
|
29 |
|
30 |
private void Insert(T[] itemArray, int indexInsertingAt, int indexInsertingFrom) |
31 |
{
|
32 |
// itemArray = 0 1 2 4 5 6 3 7
|
33 |
// insertingAt = 3
|
34 |
// insertingFrom = 6
|
35 |
// actions
|
36 |
// 1: Store index at in temp temp = 4
|
37 |
// 2: Set index at to index from -> 0 1 2 3 5 6 3 7 temp = 4
|
38 |
// 3: Walking backward from index from to index at + 1.
|
39 |
// Shift values from left to right once.
|
40 |
// 0 1 2 3 5 6 6 7 temp = 4
|
41 |
// 0 1 2 3 5 5 6 7 temp = 4
|
42 |
// 4: Write temp value to index at + 1.
|
43 |
// 0 1 2 3 4 5 6 7 temp = 4
|
44 |
|
45 |
// Step 1.
|
46 |
T temp = itemArray[indexInsertingAt]; |
47 |
|
48 |
// Step 2.
|
49 |
|
50 |
itemArray[indexInsertingAt] = itemArray[indexInsertingFrom]; |
51 |
|
52 |
// Step 3.
|
53 |
for (int current = indexInsertingFrom; current > indexInsertingAt; current--) |
54 |
{
|
55 |
itemArray[current] = itemArray[current - 1]; |
56 |
}
|
57 |
|
58 |
// Step 4.
|
59 |
itemArray[indexInsertingAt + 1] = temp; |
60 |
}
|
Auswahl Sortieren
| Verhalten | Sortiert das Eingabearray mithilfe des Auswahlsortieralgorithmus. | ||
| Komplexität | Besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O(n) | O(n2) | O(n2) |
| Raum | O(1) | O(1) | O(1) |
Die Auswahlsortierung ist eine Art Hybrid zwischen Blasensortierung und Einfügesortierung. Wie beim Sortieren von Blasen wird das Array verarbeitet, indem es immer wieder vom Anfang bis zum Ende iteriert, einen Wert auswählt und an die richtige Stelle verschiebt. Im Gegensatz zur Blasensortierung wird jedoch eher der kleinste unsortierte Wert als der größte ausgewählt. Wie bei der Einfügesortierung ist der sortierte Teil des Arrays der Anfang des Arrays, während bei der Blasensortierung der sortierte Teil am Ende ist.
Lassen Sie uns sehen, wie dies mit demselben unsortierten Array funktioniert, das wir verwendet haben.
Beim ersten Durchgang versucht der Algorithmus, den kleinsten Wert im Array zu finden und in den ersten Index zu setzen. Dies wird vom FindIndexOfSmallestFromIndex ausgeführt, der 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, sodass er sich bereits an der richtigen Stelle befindet. Zu diesem Zeitpunkt wissen wir, dass der Wert im Array-Index Null der kleinste Wert ist und daher in der richtigen Sortierreihenfolge liegt. Jetzt können wir also mit dem zweiten Durchgang beginnen - diesmal nur mit Blick auf die Array-Einträge eins bis n-1.
Der zweite Durchgang bestimmt, dass vier der kleinste Wert im unsortierten Bereich ist, und tauscht den Wert im zweiten Steckplatz gegen den Wert in dem Steckplatz, in dem vier gehalten wurden (Vertauschen der vier und sieben). Nachdem der zweite Durchgang abgeschlossen ist, wird der Wert vier an seiner sortierten Position eingefügt.
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 beendet ist, wird der sortierte Teil des Arrays größer und der unsortierte Teil wird kleiner. Wenn zu irgendeinem Zeitpunkt auf dem Weg keine Einfügungen durchgeführt werden, ist bekannt, dass das Array sortiert ist. Andernfalls wird der Vorgang fortgesetzt, bis bekannt ist, dass das gesamte Array sortiert ist.
Nach zwei weiteren Durchgängen wird das Array sortiert:
1 |
public void Sort(T[] items) |
2 |
{
|
3 |
int sortedRangeEnd = 0; |
4 |
|
5 |
while (sortedRangeEnd < items.Length) |
6 |
{
|
7 |
int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); |
8 |
Swap(items, sortedRangeEnd, nextIndex); |
9 |
|
10 |
sortedRangeEnd++; |
11 |
}
|
12 |
}
|
13 |
|
14 |
private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd) |
15 |
{
|
16 |
T currentSmallest = items[sortedRangeEnd]; |
17 |
int currentSmallestIndex = sortedRangeEnd; |
18 |
|
19 |
for (int i = sortedRangeEnd + 1; i < items.Length; i++) |
20 |
{
|
21 |
if (currentSmallest.CompareTo(items[i]) > 0) |
22 |
{
|
23 |
currentSmallest = items[i]; |
24 |
currentSmallestIndex = i; |
25 |
}
|
26 |
}
|
27 |
|
28 |
return currentSmallestIndex; |
29 |
}
|
Zusammenführen, sortieren
| Verhalten | Sortiert das Eingabearray mithilfe des Merge-Sortieralgorithmus. | ||
| Komplexität | Besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O (n log n) | O (n log n) | O (n log n) |
| Raum | O(n) | O(n) | O(n) |
Teilen und erobern
Bisher haben wir Algorithmen gesehen, die durch lineare Verarbeitung des Arrays arbeiten. Diese Algorithmen haben den Vorteil, dass sie mit sehr geringem Speicheraufwand arbeiten, jedoch auf Kosten der quadratischen Laufzeitkomplexität. Mit Merge Sort sehen wir unseren ersten Divide and Conquer-Algorithmus.
Divide and Conquer-Algorithmen zerlegen große Probleme in kleinere, leichter lösbare Probleme. Wir sehen diese Art von Algorithmen im Alltag. Zum Beispiel verwenden wir einen Divide and Conquer-Algorithmus, wenn wir ein Telefonbuch durchsuchen.
Wenn Sie den Namen Erin Johnson in einem Telefonbuch finden möchten, beginnen Sie nicht bei A und blättern Seite für Seite vorwärts. Vielmehr würden Sie wahrscheinlich das Telefonbuch in der Mitte öffnen. Wenn Sie sich für die Ms öffnen würden, würden Sie ein paar Seiten zurückblättern, vielleicht ein bisschen zu weit - die Hs vielleicht. Dann würden Sie vorwärts blättern. Und Sie blätterten in immer kleineren Schritten hin und her, bis Sie schließlich die gewünschte Seite fanden (oder so nah waren, dass ein Vorwärtsblättern Sinn machte).
Wie effizient sind Divide and Conquer-Algorithmen?
Angenommen, das Telefonbuch ist 1000 Seiten lang. Wenn Sie sich zur Mitte öffnen, haben Sie das Problem in zwei 500-Seiten-Probleme unterteilt. Angenommen, Sie befinden sich nicht auf der richtigen Seite, können Sie jetzt die entsprechende Seite für die Suche auswählen und das Problem erneut halbieren. Jetzt beträgt Ihr Problemraum 250 Seiten. Da sich das Problem immer weiter halbiert, können wir sehen, dass ein 1000-seitiges Telefonbuch in nur zehn Seitenblättern durchsucht werden kann. Dies ist 1% der Gesamtzahl der Seitenumbrüche, die bei einer linearen Suche erforderlich sein können.
Zusammenführen, sortieren
Beim Zusammenführen wird das Array immer wieder halbiert, bis jedes Stück nur noch ein Element lang ist. Dann werden diese Elemente in Sortierreihenfolge wieder zusammengesetzt (zusammengeführt).
Beginnen wir mit dem folgenden Array:
Und jetzt schneiden wir das Array in zwei Hälften:
Jetzt werden diese beiden Arrays wiederholt in zwei Hälften geschnitten, bis jedes Element für sich ist:
Da das Array jetzt in die kleinstmöglichen Teile unterteilt ist, werden diese Teile in Sortierreihenfolge wieder zusammengeführt.
Die einzelnen Elemente werden zu sortierten Zweiergruppen, diese Zweiergruppen werden zu sortierten Vierergruppen zusammengeführt, und schließlich werden alle als endgültig sortiertes Array wieder zusammengeführt.
Nehmen wir uns einen Moment Zeit, um über die einzelnen Operationen nachzudenken, die wir implementieren müssen:
- Eine Möglichkeit, die Arrays rekursiv zu teilen. Die
Sortmethode führt dies aus. - Eine Möglichkeit, die Elemente in Sortierreihenfolge zusammenzuführen. Die
Merge-Methode führt dies aus.
Eine Leistungsüberlegung der Zusammenführungssortierung besteht darin, dass die Zusammenführungssortierung im Gegensatz zu den linearen Sortieralgorithmen ihre gesamte Aufteilungs- und Zusammenführungslogik einschließlich aller Speicherzuordnungen ausführt, selbst wenn das Array bereits in sortierter Reihenfolge vorliegt. Während es eine bessere Worst-Case-Leistung als die linearen Sortieralgorithmen aufweist, ist seine Best-Case-Leistung immer schlechter. Dies bedeutet, dass es kein idealer Kandidat für die Sortierung von Daten ist, von denen bekannt ist, dass sie nahezu sortiert sind. Zum Beispiel beim Einfügen von Daten in ein bereits sortiertes Array.
1 |
public void Sort(T[] items) |
2 |
{
|
3 |
if (items.Length <= 1) |
4 |
{
|
5 |
return; |
6 |
}
|
7 |
|
8 |
int leftSize = items.Length / 2; |
9 |
int rightSize = items.Length - leftSize; |
10 |
|
11 |
T[] left = new T[leftSize]; |
12 |
T[] right = new T[rightSize]; |
13 |
|
14 |
Array.Copy(items, 0, left, 0, leftSize); |
15 |
Array.Copy(items, leftSize, right, 0, rightSize); |
16 |
|
17 |
Sort(left); |
18 |
Sort(right); |
19 |
Merge(items, left, right); |
20 |
}
|
21 |
|
22 |
private void Merge(T[] items, T[] left, T[] right) |
23 |
{
|
24 |
int leftIndex = 0; |
25 |
int rightIndex = 0; |
26 |
int targetIndex = 0; |
27 |
|
28 |
int remaining = left.Length + right.Length; |
29 |
|
30 |
while(remaining > 0) |
31 |
{
|
32 |
if (leftIndex >= left.Length) |
33 |
{
|
34 |
items[targetIndex] = right[rightIndex++]; |
35 |
}
|
36 |
else if (rightIndex >= right.Length) |
37 |
{
|
38 |
items[targetIndex] = left[leftIndex++]; |
39 |
}
|
40 |
else if (left[leftIndex].CompareTo(right[rightIndex]) < 0) |
41 |
{
|
42 |
items[targetIndex] = left[leftIndex++]; |
43 |
}
|
44 |
else
|
45 |
{
|
46 |
items[targetIndex] = right[rightIndex++]; |
47 |
}
|
48 |
|
49 |
targetIndex++; |
50 |
remaining--; |
51 |
}
|
52 |
}
|
Schnelle Sorte
| Verhalten | Sortiert das Eingabearray mithilfe des Schnellsortieralgorithmus. | ||
| Komplexität | Besten fall | Durchschnittlicher Fall | Schlimmsten Fall |
| Zeit | O(n log n) | O(n log n) | O(n2) |
| Raum | O(1) | O(1) | O(1) |
Die schnelle Sortierung ist ein weiterer Sortieralgorithmus zum Teilen und Erobern. Dieser funktioniert durch rekursives Ausführen des folgenden Algorithmus:
- Wählen Sie einen Pivot-Index und partitionieren Sie das Array in zwei Arrays. Dies erfolgt mit einer Zufallszahl im Beispielcode. Obwohl es andere Strategien gibt, habe ich für diese Stichprobe einen einfachen Ansatz bevorzugt.
- Setzen Sie alle Werte, die kleiner als der Pivot-Wert sind, links vom Pivot-Punkt und die Werte über dem Pivot-Wert rechts. Der Drehpunkt ist jetzt sortiert - alles rechts ist größer; alles links ist kleiner. Der Wert am Drehpunkt befindet sich an der richtigen sortierten Position.
- Wiederholen Sie den Pivot- und Partitionsalgorithmus für die unsortierten linken und rechten Partitionen, bis sich jedes Element an seiner bekannten sortierten Position befindet.
Führen Sie eine schnelle Sortierung für das folgende Array durch:
Schritt eins besagt, dass wir den Partitionspunkt anhand eines zufälligen Index auswählen. Im Beispielcode erfolgt dies in dieser Zeile:
1 |
int pivotIndex = _pivotRng.Next(left, right); |
Nachdem wir den Partitionsindex (vier) kennen, betrachten wir den Wert an diesem Punkt (sechs) und verschieben die Werte im Array so, dass sich alles, was kleiner als der Wert ist, 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 über die Partitionsmethode im Beispielcode.
Zu diesem Zeitpunkt wissen wir, dass sich sechs an der richtigen Stelle im Array befindet. Wir wissen das, weil jeder Wert links kleiner als der Partitionswert ist und alles rechts größer oder gleich dem Partitionswert ist. Jetzt wiederholen wir diesen Vorgang auf den beiden 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 am Index eins mit dem Wert fünf partitioniert wird. 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 verstärken, dass Sie einen Partitionswert auswählen, keinen Partitionsindex.
Wieder schnelles Sortieren:
Und ein letztes Mal schnell sortieren:
Da nur noch ein unsortierter Wert übrig ist und wir wissen, dass jeder andere Wert sortiert ist, ist das Array vollständig sortiert.
1 |
Random _pivotRng = new Random(); |
2 |
|
3 |
public void Sort(T[] items) |
4 |
{
|
5 |
quicksort(items, 0, items.Length - 1); |
6 |
}
|
7 |
|
8 |
private void quicksort(T[] items, int left, int right) |
9 |
{
|
10 |
if (left < right) |
11 |
{
|
12 |
int pivotIndex = _pivotRng.Next(left, right); |
13 |
int newPivot = partition(items, left, right, pivotIndex); |
14 |
|
15 |
quicksort(items, left, newPivot - 1); |
16 |
quicksort(items, newPivot + 1, right); |
17 |
}
|
18 |
}
|
19 |
|
20 |
private int partition(T[] items, int left, int right, int pivotIndex) |
21 |
{
|
22 |
T pivotValue = items[pivotIndex]; |
23 |
|
24 |
Swap(items, pivotIndex, right); |
25 |
|
26 |
int storeIndex = left; |
27 |
|
28 |
for (int i = left; i < right; i++) |
29 |
{
|
30 |
if (items[i].CompareTo(pivotValue) < 0) |
31 |
{
|
32 |
Swap(items, i, storeIndex); |
33 |
storeIndex += 1; |
34 |
}
|
35 |
}
|
36 |
|
37 |
Swap(items, storeIndex, right); |
38 |
return storeIndex; |
39 |
}
|
Schlussfolgerung
Damit ist der letzte Teil von Data Structures prägnant abgeschlossen: Teil 1. In dieser siebenteiligen Serie haben wir mehr über verknüpfte Listen, Arrays, den binären Suchbaum und die Set-Sammlung erfahren. Schließlich erklärte Robert die Algorithmen hinter jeder diskutierten Datenstruktur.
By
