L’ordinamento per inserzione è un algoritmo di ordinamento. È in grado di collocare i vari elementi non ordinati nelle posizioni più adatte a loro a ogni singola iterazione. Si può dire che questo algoritmo funziona in modo abbastanza simile a come si ordinano le carte in mano. Se avete esperienza di giochi di carte, saprete che i giocatori di carte ordinano con il presupposto che le prime carte siano già ordinate, dopodiché selezionano quelle non ordinate.
Nel caso in cui la carta non ordinata risulti più grande di quella in mano al giocatore, quest’ultimo deve posizionarla a destra. Altrimenti, devono tenere la carta sul lato sinistro. Allo stesso modo, si devono posizionare le altre carte non ordinate e tenerle nei rispettivi posti. L’approccio utilizzato dall’ordinamento per inserzione è molto simile a questo.
Le basi del funzionamento dell’ordinamento per inserimento
Di seguito sono riportate tre fasi che illustrano il funzionamento dell’ordinamento per inserzione:
- Nel primo passo, gli elementi in questione vengono confrontati con gli elementi adiacenti.
- Se da ogni confronto risulta che l’elemento in questione può essere utilizzato in una posizione specifica, allora viene creato uno spazio per esso. Ciò avviene spostando a destra la posizione degli altri elementi.
- Questa procedura continua finché ogni elemento presente nell’array non trova la sua giusta posizione.
Caratteristiche dell’ordinamento a inserzione
Sebbene questo algoritmo di ordinamento in-place abbia un’ampia gamma di caratteristiche, ve ne sono tre importanti che tutti devono conoscere.
- In primo luogo, l’algoritmo di ordinamento per inserzione è incredibilmente semplice. Alcuni direbbero addirittura che è il più semplice in assoluto, grazie alla sua semplice implementazione.
- Se siete programmatori che hanno a che fare regolarmente con piccoli valori di dati, l’uso di questo algoritmo vi sarà molto utile.
- La natura dell’algoritmo di ordinamento per inserzione è abbastanza adattabile, il che lo rende ideale per gli insiemi di dati parzialmente ordinati.
Domande comuni sull’ordinamento per inserzione
Ecco un elenco di risposte concise alle domande più frequenti sugli algoritmi di ordinamento per inserzione.
Quali sono i casi limite dell’algoritmo di ordinamento per inserzione?
L’ordinamento per inserimento richiede molto tempo quando si tratta di ordinare elementi in ordine inverso. Tuttavia, se gli elementi sono già ordinati, non richiede molto tempo.
Gli algoritmi di ordinamento per inserzione sono stabili?
Gli algoritmi di ordinamento per inserzione sono incredibilmente stabili, soprattutto se confrontati con altri algoritmi.
Quando è meglio usare l’algoritmo di ordinamento per inserzione?
Come accennato in precedenza, l’ordinamento per inserzione viene spesso utilizzato in presenza di una piccola quantità di elementi. Detto questo, può essere utile anche quando un array di input non ha bisogno di un ordinamento eccessivo e presenta solo pochi elementi fuori posto.
Quale approccio segue l’ordinamento per inserzione?
L’approccio seguito dall’algoritmo di ordinamento per inserzione è incrementale, motivo per cui è incredibilmente popolare tra i programmatori che si occupano di ordinare gli array.
Spiegazione dell’ordinamento binario a inserzione
I programmatori possono utilizzare la ricerca binaria per ridurre la quantità di confronti presenti nel normale ordinamento a inserzione. L’ordinamento a inserzione binaria utilizza la ricerca per trovare la posizione ideale per inserire l’elemento scelto a ogni singola iterazione. Quando si tratta di inserimento regolare, l’ordinamento utilizza O(i) (all’iesima iterazione) nel peggiore dei casi.
Possiamo usare la ricerca binaria per ridurlo a questo: O(logi). Detto questo, tuttavia, l’algoritmo ha ancora un tempo di esecuzione di circa O(n^2) per i casi peggiori. Ciò è dovuto alla quantità di scambi necessari per ogni inserimento.
Passi per l’implementazione dell’ordinamento per inserzione in elenchi collegati
I passaggi indicati di seguito mostrano come si può utilizzare l’algoritmo di ordinamento a inserzione in un elenco collegato.
- Si inizia con lo sviluppo di un elenco ordinato, assicurandosi che sia vuoto.
- Percorrere l’elenco creato e seguire questa procedura per ogni nodo
- Inserire il nodo corrente sotto forma di risultato o di elenco ordinato
- Infine, cambiare la testa dell’elenco collegato, rendendola testa dell’elenco ordinato, anche detto elenco di risultati.
Le principali applicazioni dell’ordinamento per inserzione
Ecco due degli scenari più comuni in cui i programmatori utilizzano l’ordinamento per inserzione.
– In primo luogo, lo si usa ogni volta che c’è un array con pochi elementi.
– L’ordinamento per inserzione può essere utile anche quando il numero di elementi da ordinare è ridotto.
Complessità temporali dell’ordinamento a inserzione
Ecco un’analisi delle complessità temporali che si possono incontrare nell’ordinamento per inserzione.
Complessità del caso peggiore O (n2) – Worst Case Complexity O (n2)
Immaginiamo che un array sia presente in ordine crescente e che si voglia ordinarlo in ordine decrescente. Un caso come questo dà luogo alla complessità del caso peggiore. In questa situazione, è necessario confrontare ogni elemento con altri elementi per garantire che ci siano (n-1) confronti per ogni nesimo elemento.
La quantità totale di confronti sarà n*(n-1) ~ n2
Caso medio Complessità O(n) – Average Case Complexity O(n)
Questo tipo di complessità si verifica spesso quando gli elementi di un array sono confusi, ovvero non sono né in ordine decrescente né in ordine crescente.
Complessità spaziale – Space Complexity
La complessità spaziale diventa 0(1) ogni volta che viene implementata una variabile extra.
Complessità del caso migliore – Best Case Complexity
Quando un array non richiede alcun ordinamento, il numero di volte in cui il ciclo esterno viene eseguito è n. D’altra parte, il ciclo interno rimane inattivo e non esegue alcuna operazione. Ciò significa che la quantità di confronti sarà pari a n, con conseguente complessità lineare.
Analisi della complessità temporale
Sebbene sia innegabile l’efficienza dell’ordinamento per inserzione, se si fornisce un array già ordinato all’ordinamento per inserzione, l’algoritmo continuerà a eseguire l’altro ciclo. Ciò richiederà n passaggi per ordinare un array di n elementi che sono già stati ordinati all’inizio, trasformando essenzialmente la complessità temporale del caso migliore in una funzione lineare n.
Un array non ordinato richiede un elemento per fare confronti con altri elementi, il che significa che ogni elemento di n viene confrontato con altri n elementi. Sarebbe utile anche analizzare altri algoritmi simili, come Quick Sort, Merge Sort o Selection Sort, per valutarne la rispettiva complessità.
