Komplexität der Einfüge-Sortierzeit

Betrachten Sie die folgenden Zahlen:

50 60 30 10 80 70 20 40

Wenn diese Liste aufsteigend sortiert wäre, wäre es:

10 20 30 40 50 60 70 80

Absteigend sortiert wäre das:

80 70 60 50 40 30 20 10

Einfügungssortierung ist ein Sortieralgorithmus, der verwendet wird, um die Liste in aufsteigender Reihenfolge oder in absteigender Reihenfolge zu sortieren. Dieser Artikel befasst sich nur mit der Sortierung in aufsteigender Reihenfolge. Das Sortieren in absteigender Reihenfolge folgt der gleichen Logik wie in diesem Dokument. Das Ziel dieses Artikels ist es, die Einfügesortierung zu erklären. Die Programmierung erfolgt im folgenden Beispiel in C. Die Einfügesortierung wird hier anhand eines Arrays erklärt.

Algorithmus für Insertion Sort

Es wird eine unsortierte Liste ausgegeben. Ziel ist es, die Liste anhand derselben Liste in aufsteigender Reihenfolge zu sortieren. Das Sortieren eines unsortierten Arrays mit demselben Array wird als direktes Sortieren bezeichnet. Hier wird die nullbasierte Indizierung verwendet. Die Schritte sind wie folgt:

• • Die Liste wird von Anfang an gescannt.
  • Während des Scannens wird jede Nummer kleiner als sein Vorgänger mit seinem Vorgänger ausgetauscht.
  • Dieses Vertauschen wird entlang der Liste fortgesetzt, bis ein Vertauschen nicht mehr möglich ist.
  • Wenn das Scannen das Ende erreicht, ist die Sortierung abgeschlossen.

Einfügen sortieren Abbildung

Beim Umgang mit zeitlicher Komplexität wird normalerweise der ungünstigste Fall berücksichtigt. Die schlechteste Anordnung für die vorherige Liste ist:

80 70 60 50 40 30 20 10

Es gibt acht Elemente mit Indizes von null bis 7.

Bei Index Null geht die Abtastung auf 80. Dies ist eine Bewegung. Diese eine Bewegung ist eine Operation. Bisher gibt es insgesamt eine Operation (eine Bewegung, kein Vergleich und kein Tausch). Das Ergebnis ist:

| 80 70 60 50 40 30 20 10

Bei Index eins gibt es eine Bewegung auf 70. 70 wird mit 80 verglichen. 70 und 80 werden getauscht. Eine Bewegung ist eine Operation. Ein Vergleich ist auch eine Operation. Ein Austausch ist auch ein Vorgang. Dieser Abschnitt enthält drei Operationen. Bisher gibt es insgesamt vier Operationen (1 + 3 = 4). Das Ergebnis ist wie folgt:

70 | 80 60 50 40 30 20 10

Bei Index zwei gibt es eine Bewegung auf 60. 60 wird mit 80 verglichen, dann werden 60 und 80 getauscht. 60 wird mit 70 verglichen, dann werden 60 und 70 vertauscht. Eine Bewegung ist eine Operation. Zwei Vergleiche sind zwei Operationen. Zwei Swaps sind zwei Operationen. Dieser Abschnitt enthält fünf Operationen. Bisher gibt es insgesamt neun Operationen (4 + 5 = 9). Das Ergebnis ist wie folgt:

60 70 | 80 50 40 30 20 10

Bei Index drei gibt es eine Bewegung auf 50. 50 wird mit 80 verglichen, dann werden 50 und 80 getauscht. 50 wird mit 70 verglichen, dann werden 50 und 70 vertauscht. 50 wird mit 60 verglichen, dann werden 50 und 60 vertauscht. Eine Bewegung ist eine Operation. Drei Vergleiche sind drei Operationen. Drei Swaps sind drei Operationen. Dieser Abschnitt enthält sieben Operationen. Bisher gibt es insgesamt sechzehn Operationen (9 + 7 = 16). Das Ergebnis ist wie folgt:

50 60 70 | 80 40 30 20 10

Bei Index vier gibt es eine Bewegung auf 40. 40 wird mit 80 verglichen, dann werden 40 und 80 vertauscht. 40 wird mit 70 verglichen, dann werden 40 und 70 vertauscht. 40 wird mit 60 verglichen, dann werden 40 und 60 vertauscht. 40 wird mit 50 verglichen, dann werden 40 und 50 vertauscht. Eine Bewegung ist eine Operation. Vier Vergleiche sind vier Operationen. Vier Swaps sind vier Operationen. Dieser Abschnitt enthält neun Operationen. Bisher gibt es insgesamt fünfundzwanzig Operationen (16 + 9 = 25). Das Ergebnis ist wie folgt:

40 50 60 70 80 | 30 20 10

Bei Index fünf gibt es eine Bewegung auf 30. 30 wird mit 80 verglichen, dann werden 30 und 80 getauscht. 30 wird mit 70 verglichen, dann werden 30 und 70 vertauscht. 30 wird mit 60 verglichen, dann werden 30 und 60 vertauscht. 30 wird mit 50 verglichen, dann werden 30 und 50 vertauscht. 30 wird mit 40 verglichen, dann werden 30 und 40 vertauscht. Eine Bewegung ist eine Operation. Fünf Vergleiche sind fünf Operationen. Fünf Swaps sind fünf Operationen. Dieser Abschnitt enthält elf Operationen. Bisher gibt es insgesamt sechsunddreißig Operationen (25 + 11 = 36). Das Ergebnis ist wie folgt:

30 40 50 60 70 80 | 20 10

Bei Index sechs gibt es eine Bewegung auf 20. 20 wird mit 80 verglichen, dann werden 20 und 80 getauscht. 20 wird mit 70 verglichen, dann werden 20 und 70 vertauscht. 20 wird mit 60 verglichen, dann werden 20 und 60 vertauscht. 20 wird mit 50 verglichen, dann werden 20 und 50 vertauscht. 20 wird mit 40 verglichen, dann werden 20 und 40 vertauscht. 20 wird mit 30 verglichen, dann werden 20 und 30 vertauscht. Eine Bewegung ist eine Operation. Sechs Vergleiche sind sechs Operationen. Sechs Swaps sind sechs Operationen. Dieser Abschnitt enthält dreizehn Operationen. Bisher gibt es insgesamt neunundvierzig Operationen (36 + 13 = 49). Das Ergebnis ist wie folgt:

20 30 40 50 60 70 80 | 10

Bei Index sieben gibt es eine Bewegung auf 10. 10 wird mit 80 verglichen, dann werden 10 und 80 vertauscht. 10 wird mit 70 verglichen, dann werden 10 und 70 vertauscht. 10 wird mit 60 verglichen, dann werden 10 und 60 vertauscht. 10 wird mit 50 verglichen, dann werden 10 und 50 vertauscht. 10 wird mit 30 verglichen, dann werden 10 und 40 vertauscht. 10 wird mit 30 verglichen, dann werden 10 und 30 vertauscht. 10 wird mit 20 verglichen, dann werden 10 und 20 vertauscht. Eine Bewegung ist eine Operation. Sieben Vergleiche sind sieben Operationen. Sieben Swaps sind sieben Operationen. Dieser Abschnitt enthält fünfzehn Operationen. Bisher gibt es insgesamt vierundsechzig Operationen (49 + 15 = 64). Das Ergebnis ist wie folgt:

10 20 30 40 50 60 70 80 10 |

Die Arbeit ist erledigt! 64 Operationen waren beteiligt.

64 = 8 x 8 = 8 ^zwei

Zeitkomplexität für Insertion Sort

Wenn n Elemente mit Insertion Sort zu sortieren sind, wäre die maximale Anzahl möglicher Operationen n2, wie zuvor gezeigt. Die Komplexität der Insertion Sort Time beträgt:

An ^zwei )

Dies verwendet die Big-O-Notation. Die Big-O-Notation beginnt mit O in Großbuchstaben, gefolgt von Klammern. Innerhalb der Klammern steht der Ausdruck für die maximal mögliche Anzahl von Operationen.

Codierung in C

Ganz am Anfang des Scans kann das erste Element seine Position nicht ändern. Das Programm sieht im Wesentlichen wie folgt aus:

Die Funktionsdefinition insertSort() verwendet den beschriebenen Algorithmus. Beachten Sie die Bedingungen für die While-Schleife. Eine geeignete C-Hauptfunktion für dieses Programm ist:

Fazit

Die Zeitkomplexität für Insertion Sort wird wie folgt angegeben:

An ^zwei )

Der Leser hat vielleicht von Zeitkomplexität im schlimmsten Fall, Zeitkomplexität im durchschnittlichen Fall und Zeitkomplexität im besten Fall gehört. Diese Variationen der Insertion Sort Time Complexity werden im nächsten Artikel auf unserer Website besprochen.