Nach Einsätzen sortieren

Hallo. Heute setzen wir die Artikelserie fort, die ich speziell für den Start des Kurses "Algorithmen und Datenstrukturen" von OTUS geschrieben habe.

---

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 Schreibens und die entsprechenden Fragen häufig in Interviews als Praktikant oder Nachwuchsentwickler 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.

Nach Einsätzen sortieren

Das letzte Mal haben wir über eine der einfachsten Sorten gesprochen - die Auswahlsorte . Heute konzentrieren wir uns auf einen etwas komplexeren Algorithmus - die Einfügungssortierung.

Algorithmusbeschreibung

Das Sortieren eines Arrays nach Einfügungen erfolgt folgendermaßen: Genau wie bei der Auswahlsortierung wird das Array in zwei Teile unterteilt. Ein Teil heißt sortiert und der andere unsortiert. Der Algorithmus geht davon aus, dass das gesamte Array durchlaufen wird, sodass die Länge des sortierten Teils der Länge des gesamten Arrays entspricht. Innerhalb jeder Iteration nehmen wir das erste Element des unsortierten Teils des Arrays und führen die folgende Operation damit aus: Während unser Element streng kleiner als das vorherige ist, tauschen wir sie aus. Dann erhöhen wir die Länge des sortierten Teils des Arrays um eins. Indem wir das zu untersuchende Element nacheinander bewegen, erreichen wir, dass es an seinen Platz fällt. Ein Beispiel für eine Iteration ist unten dargestellt:

1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Implementierung

Ich schlage vor, die Implementierung dieses Algorithmus in C zu betrachten:

void insertionSortFunction(double array[], int size) {
    int i, j, temp;
    // i     ,   1,         
    for (i = 1; i < size; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] < temp) {
                break;
            }
  
            array[j + 1] = array[j];
            array[j] = temp;
        }
    }
}

Analyse

Ich schlage vor, diesen Algorithmus zu analysieren.



Der einfachste Weg, um die Analyse zu starten, besteht darin, die Asymptotik des Gedächtnisses zu ermitteln. Unabhängig von der Länge und Struktur des zum Sortieren vorgeschlagenen Arrays wird der Speicher nur für zwei Schleifenzähler und eine Hilfsvariable zugewiesen, die zum Austausch von zwei Variablenwerten verwendet werden. Somit ist es immer wahr:

$$

$$M(n) = O(1)$$

.



Mit der Zeit ist alles etwas interessanter. Der Körper der inneren Schleife selbst nimmt O (1), das heißt, es hängt nicht von der Größe des zu sortierenden Arrays ab. Dies bedeutet, dass zum Verständnis der Asymptotik des Algorithmus gezählt werden muss, wie oft dieser Körper ausgeführt wird. Die Anzahl der Iterationen der inneren Schleife hängt jedoch davon ab, wie gut geordnet (oder ungeordnet) die Elemente des zu sortierenden Arrays sind. Für die Analyse müssen mehrere Fälle untersucht werden.



Die Mindestanzahl von Iterationen ist erreicht, wenn das zu sortierende Array bereits sortiert ist. In der Tat tritt für jede Iteration der äußeren for-Schleife genau eine Iteration der inneren Schleife auf. Dies ist der sogenannte beste Fall .

$$

$$T(n) = (n - 1) * O(1) = O(n)$$

Somit erfolgt die Sortierung in linearer Zeit.



Im schlimmsten Fall wird angenommen, dass die Anzahl der Iterationen am größten ist, dh, Pause wird niemals ausgelöst. Bei der ersten Iteration der äußeren Schleife wird eine Iteration der inneren Schleife durchgeführt. Bei der zweiten Iteration der äußeren Schleife werden 2 Iterationen der inneren Schleife durchgeführt. Wenn wir die Argumentation weiter fortsetzen, können wir zu dem Schluss kommen, dass bei der letzten (n - 1) - th) Iteration der äußeren Schleife (n - 1) die Iteration der inneren Schleife ausgeführt wird. Wir bekommen:

$$

$$T(n) = O(1) + 2 * O(1) + 3 * O(1) + ... + (n - 1) * O(1) = O(1 + 2 + 3 + ... + (n - 1)) = O(n * (n - 1) / 2) = O(n ^ 2)$$

Zur Durchführung der Berechnungen verwendeten wir die Eigenschaften der O-Notation und die Formel für die Summe einer arithmetischen Folge.



Im Durchschnittsfall wird angenommen, dass die Anzahl der Iterationen der inneren Schleife für eine bestimmte Iteration der äußeren Schleife gleich ihrem Durchschnittswert ist, dh der mathematischen Erwartung. Angenommen, alle zulässigen Zahlen des Zündens der inneren Schleife sind gleich wahrscheinlich. In diesem Fall beträgt die durchschnittliche Anzahl von Iterationen der inneren Schleife . Es wird angenommen, dass I die Iterationsnummer der äußeren Schleife ist. Um nun die Asymptotik zu berechnen, müssen Sie berechnen . Das heißt, wir zählen nur, wie oft der Körper der inneren Schleife ausgeführt wird. So bekommen wir .



Zusammenfassend ist die Speicherasymptotik des Algorithmus

$$

$$O(1)$$

bestenfalls rechtzeitig

$$

$$O(n)$$

und im Durchschnitt und im schlimmsten Fall

$$

$$O(n^2)$$

Daher gehört diese Sortierung zur Klasse der quadratischen Sortierungen .



Es ist auch wichtig zu beachten, dass die Auswahlsortierung in dieser Implementierung robust ist . Ich möchte Sie daran erinnern, dass die Sortierung als stabil bezeichnet wird, wenn sich die Reihenfolge der gleichen Elemente während ihrer Ausführung nicht ändert. Diese Eigenschaft ist für eine Bildungsaufgabe wie das Sortieren eines Arrays von Zahlen nicht sehr wichtig. Wenn wir jedoch einige komplexere Objekte mit einer festgelegten Ordnungsbeziehung sortieren, ist dies möglicherweise wichtig. Wir können ein ähnliches Beispiel betrachten, wenn wir das nächste Mal über Radix-Sortierung sprechen.

Ergebnis

Wir haben uns eine andere quadratische Sortierung angesehen: die Einfügungssortierung und ihre robuste Implementierung. Das Sortieren ist meistens lehrreich, obwohl es in der Praxis bestenfalls aufgrund einer guten Asymptotik angewendet werden kann: Wenn Sie einer ausreichend großen geordneten Datenmenge neue Daten hinzufügen müssen, damit alle Daten erneut geordnet werden, kann die innere for-Schleife nützlich sein. So kann es unterstützt werden für

$$

$$O(n)$$

Ordnung des Datenvolumens.

---

Erfahren Sie mehr über den Kurs.

---