Insertion Sortierzeit Komplexität

Betrachten Sie die folgenden Zahlen:

50 60 30 10 80 70 20 40

Wenn diese Liste in aufsteigender Reihenfolge sortiert ist, wäre dies:

10 20 30 40 50 60 70 80

Wenn es in absteigender Reihenfolge sortiert ist, wäre es:

80 70 60 50 40 30 20 10

Insertion -Sortierung ist ein Sortieralgorithmus, mit dem die Liste in aufsteigender Reihenfolge oder in absteigender Reihenfolge sortiert wird. Dieser Artikel befasst sich nur mit der Sortierung in aufsteigender Reihenfolge. Die Sortierung in absteigender Reihenfolge folgt der gleichen Logik, die in diesem Dokument angegeben ist. Das Ziel dieses Artikels ist es, die Insertion -Sortierung zu erklären. Die Programmierung erfolgt im folgenden Beispiel in C. Die Insertion -Sortierung wird hier mit einem Array erklärt.

Algorithmus zur Einfügungssorte

Eine unsortierte Liste wird angegeben. Ziel ist es, die Liste in aufsteigender Reihenfolge mit derselben Liste zu sortieren. Das Sortieren eines unsortierten Arrays mit demselben Array soll ein Ort sortieren. Die null basierte Indexierung wird hier verwendet. Die Schritte sind wie folgt:

• • Die Liste wird von Anfang an gescannt.
  • Während des Scannens wird eine beliebige Zahl weniger als der Vorgänger mit seinem Vorgänger getauscht.
  • Dieser Austausch wird entlang der Liste fortgesetzt, bis es nicht mehr ausgetauscht werden kann.
  • Wenn das Scannen das Ende erreicht, ist die Sortierung abgeschlossen.

Insertion -Sortierillustration

Bei der Umgang mit der Zeitkomplexität ist es der schlimmste Fall, der normalerweise berücksichtigt wird. Die schlechteste Vereinbarung 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 das Scannen auf 80. Dies ist eine Bewegung. Diese eine Bewegung ist eine Operation. Bisher gibt es insgesamt eine Operation (eine Bewegung, kein Vergleich und kein Swap). Das Ergebnis ist:

| 80 70 60 50 40 30 20 10

Bei Index 1 gibt es eine Bewegung zu 70. 70 wird mit 80 verglichen. 70 und 80 werden ausgetauscht. Eine Bewegung ist eine Operation. Ein Vergleich ist auch eine Operation. Ein Tausch ist auch eine Operation. Dieser Abschnitt enthält drei Vorgänge. Bisher gibt es insgesamt vier Operationen (1 + 3 = 4). Das Ergebnis ist wie folgt:

70 | 80 60 50 40 30 20 10 10

Bei Index zwei gibt es eine Bewegung zu 60. 60 wird mit 80 verglichen, dann werden 60 und 80 getauscht. 60 wird mit 70 verglichen, dann werden 60 und 70 getauscht. 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 10

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

50 60 70 | 80 40 30 20 10

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

40 50 60 70 80 | 30 20 10

Bei Index Five gibt es eine Bewegung zu 30. 30 wird mit 80 verglichen, dann werden 30 und 80 getauscht. 30 wird mit 70 verglichen, dann werden 30 und 70 getauscht. 30 wird mit 60 verglichen, dann werden 30 und 60 getauscht. 30 wird mit 50 verglichen, dann werden 30 und 50 ausgetauscht. 30 wird mit 40 verglichen, dann werden 30 und 40 ausgetauscht. Eine Bewegung ist eine Operation. Fünf Vergleiche sind fünf Operationen. Fünf Swaps sind fünf Operationen. Dieser Abschnitt enthält elf Vorgänge. 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 zu 20. 20 wird mit 80 verglichen, dann werden 20 und 80 getauscht. 20 wird mit 70 verglichen, dann werden 20 und 70 getauscht. 20 wird mit 60 verglichen, dann werden 20 und 60 getauscht. 20 wird mit 50 verglichen, dann werden 20 und 50 getauscht. 20 wird mit 40 verglichen, dann werden 20 und 40 ausgetauscht. 20 wird mit 30 verglichen, dann werden 20 und 30 getauscht. 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

In Index Seven gibt es eine Bewegung zu 10. 10 wird mit 80 verglichen, dann werden 10 und 80 ausgetauscht. 10 wird mit 70 verglichen, dann werden 10 und 70 getauscht. 10 wird mit 60 verglichen, dann werden 10 und 60 getauscht. 10 wird mit 50 verglichen, dann werden 10 und 50 ausgetauscht. 10 wird mit 30 verglichen, dann werden 10 und 40 ausgetauscht. 10 wird mit 30 verglichen, dann werden 10 und 30 getauscht. 10 wird mit 20 verglichen, dann werden 10 und 20 getauscht. 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 64 Operationen (49 + 15 = 64). Das Ergebnis ist wie folgt:

10 20 30 40 50 60 70 80 10 |

Der Job ist erledigt! 64 Operationen waren beteiligt.

64 = 8 x 8 = 8²

Zeitkomplexität für die Insertion -Sortierung

Wenn es N -Elemente zur Sortierung mit Insertion -Sortierungen gibt, wäre die maximale Anzahl möglicher Operationen N2, wie zuvor gezeigt. Die Komplexität der Insertion -Sortierzeit lautet:

An²)

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

Codierung in c

Zu Beginn des Scans kann das erste Element seine Position nicht ändern. Das Programm ist im Wesentlichen das folgende:

#enthalten
Hohlrauminsertionsort (int a [], int n)
für (int i = 0; iint j = i;
while (a [j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //Tausch
J--;

Die Funktionsdefinition insertionsort () verwendet den Algorithmus wie beschrieben. Beachten Sie die Bedingungen für die While-Loop. Eine geeignete C -Hauptfunktion für dieses Programm ist:

int main (int argc, char ** argv)

int n = 8;
int a [] = 50, 60, 30, 10, 80, 70, 20, 40;
Insertionsort (a, n);
für (int i = 0; iprintf ("%i", a [i]);

printf ("\ n");
Rückkehr 0;

Abschluss

Die zeitliche Komplexität für die Einfügungssorte wird angegeben als:

An²)

Der Leser hätte möglicherweise von einer schlechteren Zeitkomplexität, einer durchschnittlichen Zeitkomplexität und der Best-Case-Zeitkomplexität gehört. Diese Variationen der Insertions -Sortierzeitkomplexität werden im nächsten Artikel auf unserer Website erörtert.