Inserimento ordinare la complessità del tempo

Considera i seguenti numeri:

50 60 30 10 10 80 70 20 40

Se questo elenco viene ordinato in ordine crescente, sarebbe:

10 20 30 30 40 50 60 70 80

Se viene ordinato in ordine decrescente, sarebbe:

80 70 60 50 40 30 20 10

L'ordinamento di inserzione è un algoritmo di ordinamento che viene utilizzato per ordinare l'elenco in ordine crescente o in ordine decrescente. Questo articolo si occupa solo di ordinamento in ordine crescente. L'ordinamento in ordine decrescente segue la stessa logica fornita in questo documento. Lo scopo di questo articolo è di spiegare il tipo di inserimento. La programmazione viene eseguita nel seguente esempio in C. L'ordinamento di inserzione viene spiegato qui usando un array.

Algoritmo per ordinamento di inserimento

Viene fornito un elenco non orientato. L'obiettivo è quello di ordinare l'elenco in ordine crescente utilizzando lo stesso elenco. Si dice che l'ordinamento di un array non desiderato usando lo stesso array sia l'ordinamento sul posto. L'indicizzazione basata su zero viene utilizzata qui. I passi sono come segue:

• • L'elenco è scansionato dall'inizio.
  • Mentre la scansione è in corso, qualsiasi numero inferiore al suo predecessore viene scambiato con il suo predecessore.
  • Questo scambio continua lungo l'elenco, fino a quando non è più possibile scambiare.
  • Durante la scansione raggiunge la fine, l'ordinamento è completo.

L'inserimento dell'ordinamento illustrazione

Quando si tratta della complessità del tempo, è il caso peggiore che viene normalmente preso in considerazione. La peggiore disposizione per l'elenco precedente è:

80 70 60 50 40 30 20 10

Ci sono otto elementi con indici da zero a 7.

All'indice zero, la scansione va a 80. Questo è un movimento. Questo movimento è un'operazione. Finora c'è un totale di un'operazione (un movimento, nessun confronto e nessun scambio). Il risultato è:

| 80 70 60 50 40 30 20 10

All'indice, c'è un movimento a 70. 70 viene confrontato con 80. 70 e 80 sono scambiati. Un movimento è un'operazione. Un confronto è anche un'operazione. Uno scambio è anche un'operazione. Questa sezione fornisce tre operazioni. Finora ci sono quattro operazioni in totale (1 + 3 = 4). Il risultato è il seguente:

70 | 80 60 50 50 40 30 20 10

All'indice due, c'è un movimento a 60. 60 viene confrontato con 80, quindi 60 e 80 vengono scambiati. 60 viene confrontato con 70, quindi 60 e 70 vengono scambiati. Un movimento è un'operazione. Due confronti sono due operazioni. Due swap sono due operazioni. Questa sezione fornisce cinque operazioni. Finora ci sono un totale di nove operazioni (4 + 5 = 9). Il risultato è il seguente:

60 70 | 80 50 50 40 30 20 10

All'indice tre, c'è un movimento a 50. 50 viene confrontato con 80, quindi 50 e 80 vengono scambiati. 50 viene confrontato con 70, quindi 50 e 70 vengono scambiati. 50 vengono confrontati con 60, quindi 50 e 60 vengono scambiati. Un movimento è un'operazione. Tre confronti sono tre operazioni. Tre swap sono tre operazioni. Questa sezione fornisce sette operazioni. Finora ci sono un totale di sedici operazioni (9 + 7 = 16). Il risultato è il seguente:

50 60 70 | 80 40 30 30 20 10

All'indice quattro, c'è un movimento a 40. 40 viene confrontato con 80, quindi 40 e 80 vengono scambiati. 40 viene confrontato con 70, quindi 40 e 70 vengono scambiati. 40 viene confrontato con 60, quindi 40 e 60 vengono scambiati. 40 viene confrontato con 50, quindi 40 e 50 vengono scambiati. Un movimento è un'operazione. Quattro confronti sono quattro operazioni. Quattro swap sono quattro operazioni. Questa sezione fornisce nove operazioni. Finora ci sono un totale di venticinque operazioni (16 + 9 = 25). Il risultato è il seguente:

40 50 60 70 80 | 30 20 10

All'indice cinque, c'è un movimento a 30. 30 vengono confrontati con 80, quindi 30 e 80 vengono scambiati. 30 vengono confrontati con 70, quindi 30 e 70 vengono scambiati. 30 viene confrontato con 60, quindi 30 e 60 vengono scambiati. 30 vengono confrontati con 50, quindi 30 e 50 vengono scambiati. 30 vengono confrontati con 40, quindi 30 e 40 vengono scambiati. Un movimento è un'operazione. Cinque confronti sono cinque operazioni. Cinque swap sono cinque operazioni. Questa sezione fornisce undici operazioni. Finora ci sono un totale di trentasei operazioni (25 + 11 = 36). Il risultato è il seguente:

30 40 50 50 60 70 80 | 20 10

All'indice sei, c'è un movimento a 20. 20 viene confrontato con 80, quindi 20 e 80 vengono scambiati. 20 viene confrontato con 70, quindi 20 e 70 vengono scambiati. 20 viene confrontato con 60, quindi 20 e 60 vengono scambiati. 20 viene confrontato con 50, quindi 20 e 50 vengono scambiati. 20 viene confrontato con 40, quindi 20 e 40 vengono scambiati. 20 viene confrontato con 30, quindi 20 e 30 vengono scambiati. Un movimento è un'operazione. Sei confronti sono sei operazioni. Sei swap sono sei operazioni. Questa sezione fornisce tredici operazioni. Finora ci sono un totale di quarantanove operazioni (36 + 13 = 49). Il risultato è il seguente:

20 30 40 50 50 60 70 80 | 10

All'indice sette, c'è un movimento a 10. 10 viene confrontato con 80, quindi 10 e 80 vengono scambiati. 10 viene confrontato con 70, quindi 10 e 70 vengono scambiati. 10 viene confrontato con 60, quindi 10 e 60 vengono scambiati. 10 viene confrontato con 50, quindi 10 e 50 vengono scambiati. 10 viene confrontato con 30, quindi 10 e 40 vengono scambiati. 10 viene confrontato con 30, quindi 10 e 30 vengono scambiati. 10 viene confrontato con 20, quindi 10 e 20 vengono scambiati. Un movimento è un'operazione. Sette confronti sono sette operazioni. Sette swap sono sette operazioni. Questa sezione fornisce quindici operazioni. Finora ci sono un totale di sessantaquattro operazioni (49 + 15 = 64). Il risultato è il seguente:

10 20 30 30 40 50 60 70 80 10 |

Il lavoro è finito! 64 operazioni sono state coinvolte.

64 = 8 x 8 = 8²

Complessità temporale per l'ordinamento di inserimento

Se ci sono n elementi da ordinare con ordinamento di inserimento, il numero massimo di possibili operazioni sarebbe N2, come dimostrato in precedenza. La complessità del tempo di ordinazione dell'inserzione è:

SU²)

Questo usa la notazione Big-O. La notazione Big-O inizia con O in maiuscolo, seguita da parentesi. All'interno delle parentesi c'è l'espressione per il numero massimo possibile di operazioni.

Coding in c

All'inizio della scansione, il primo elemento non può cambiare la sua posizione. Il programma è essenzialmente il seguente:

#includere
void insertionsort (int a [], int n)
per (int i = 0; iint j = i;
mentre (a [j] < A[j-1] && j-1 >= 0)
int temp = a [j]; A [j] = a [j-1]; A [j-1] = temp; //scambio
J--;

La definizione della funzione insertionsort () utilizza l'algoritmo come descritto. Nota le condizioni per il loop while. Una funzione principale C di questo programma è:

int main (int argc, char ** argv)

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

printf ("\ n");
restituzione 0;

Conclusione

La complessità temporale per l'ordinamento di inserimento è data come:

SU²)

Il lettore potrebbe aver sentito parlare di una complessità del tempo peggiore, della complessità del tempo medio e della complessità del tempo migliore. Queste variazioni della complessità del tempo di ordinamento di inserimento sono discusse nel prossimo articolo nel nostro sito Web.