Considera i seguenti numeri:
50 60 30 10 80 70 20 40
Se questo elenco è ordinato in ordine crescente, sarebbe:
10 20 30 40 50 60 70 80
Se è ordinato in ordine decrescente, sarebbe:
80 70 60 50 40 30 20 10
L'ordinamento per inserimento è un algoritmo di ordinamento utilizzato per ordinare l'elenco in ordine crescente o decrescente. Questo articolo si occupa solo dell'ordinamento in ordine crescente. L'ordinamento in ordine decrescente segue la stessa logica data in questo documento. Lo scopo di questo articolo è spiegare l'ordinamento di inserimento. La programmazione viene eseguita nell'esempio seguente in C. L'ordinamento per inserimento è spiegato qui utilizzando un array.
Algoritmo per l'ordinamento di inserzione
Viene fornito un elenco non ordinato. L'obiettivo è ordinare l'elenco in ordine crescente utilizzando lo stesso elenco. Si dice che l'ordinamento di un array non ordinato utilizzando lo stesso array sia l'ordinamento sul posto. Qui viene utilizzata l'indicizzazione in base zero. I passi sono come segue:
-
- L'elenco viene scansionato dall'inizio.
- Durante la scansione, 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.
- Quando la scansione raggiunge la fine, l'ordinamento è completo.
Illustrazione di ordinamento di inserimento
Quando si ha a che fare con la complessità del tempo, è il caso peggiore che viene normalmente preso in considerazione. La disposizione peggiore 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. C'è un totale di un'operazione finora (un movimento, nessun confronto e nessuno scambio). Il risultato è:
| 80 70 60 50 40 30 20 10
All'indice uno, c'è un movimento a 70. 70 viene confrontato con 80. 70 e 80 vengono scambiati. Un movimento è un'operazione. Un confronto è anche un'operazione. Uno scambio è anche un'operazione. Questa sezione fornisce tre operazioni. Ci sono un totale di quattro operazioni finora (1 + 3 = 4). Il risultato è il seguente:
70 | 80 60 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 scambi sono due operazioni. Questa sezione fornisce cinque operazioni. Finora sono state effettuate nove operazioni (4 + 5 = 9). Il risultato è il seguente:
60 70 | 80 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 viene confrontato con 60, quindi 50 e 60 vengono scambiati. Un movimento è un'operazione. Tre confronti sono tre operazioni. Tre scambi sono tre operazioni. Questa sezione fornisce sette operazioni. Finora sono state effettuate sedici operazioni (9 + 7 = 16). Il risultato è il seguente:
50 60 70 | 80 40 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 scambi sono quattro operazioni. Questa sezione fornisce nove operazioni. Finora sono state effettuate 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 viene confrontato con 80, quindi 30 e 80 vengono scambiati. 30 viene confrontato con 70, quindi 30 e 70 vengono scambiati. 30 viene confrontato con 60, quindi 30 e 60 vengono scambiati. 30 viene confrontato con 50, quindi 30 e 50 vengono scambiati. 30 viene confrontato con 40, quindi 30 e 40 vengono scambiati. Un movimento è un'operazione. Cinque confronti sono cinque operazioni. Cinque scambi sono cinque operazioni. Questa sezione fornisce undici operazioni. C'è un totale di trentasei operazioni finora (25 + 11 = 36). Il risultato è il seguente:
30 40 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 scambi sono sei operazioni. Questa sezione fornisce tredici operazioni. Finora sono state effettuate quarantanove operazioni (36 + 13 = 49). Il risultato è il seguente:
20 30 40 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 scambi sono sette operazioni. Questa sezione fornisce quindici operazioni. Finora sono state effettuate sessantaquattro operazioni (49 + 15 = 64). Il risultato è il seguente:
10 20 30 40 50 60 70 80 10 |
Il lavoro è fatto! Sono state coinvolte 64 operazioni.
64 = 8 x 8 = 8 Due
Complessità temporale per l'ordinamento di inserimento
Se ci sono n elementi da ordinare con Ordinamento per inserimento, il numero massimo di operazioni possibili sarebbe n2, come dimostrato in precedenza. La complessità del tempo di ordinamento di inserimento è:
SU Due )
Questo usa la notazione Big-O. La notazione Big-O inizia con O in maiuscolo, seguita da parentesi. Tra parentesi c'è l'espressione per il numero massimo possibile di operazioni.
Codifica in C
All'inizio della scansione, il primo elemento non può cambiare la sua posizione. Il programma è essenzialmente il seguente:
#includeinserimento vuotoOrdina ( int A [ ] , int n ) {
per ( int io = 0 ; io < N; io++ ) {
int j = io;
mentre ( UN [ j ] < UN [ j- 1 ] && j- 1 > = 0 ) {
int = A [ j ] ; UN [ j ] = A [ j- 1 ] ; UN [ j- 1 ] = temp; // scambio
j--;
}
}
}
La definizione della funzione insertSort() utilizza l'algoritmo come descritto. Nota le condizioni per il ciclo while. Una funzione principale C adatta per questo programma è:
{
int n = 8 ;
int A [ ] = { cinquanta , 60 , 30 , 10 , 80 , 70 , venti , 40 } ;
inserimentoOrdina ( Un ) ;
per ( int io = 0 ; io < n; io++ ) {
stampa f ( '%io ' , UN [ io ] ) ;
}
stampa f ( ' \n ' ) ;
Restituzione 0 ;
}
Conclusione
La complessità temporale per l'ordinamento di inserimento è data come:
SU Due )
Il lettore potrebbe aver sentito parlare di complessità temporale nel caso peggiore, complessità temporale del caso medio e complessità temporale del caso migliore. Queste variazioni della complessità del tempo di ordinamento di inserimento sono discusse nel prossimo articolo nel nostro sito Web.