L’ordinamento per inserzione è un semplice algoritmo di ordinamento che funziona sulla falsariga dell’ordinamento delle carte da gioco. Non è sicuramente l’algoritmo più efficente in questo ambito, ma è sicuramente tra i più studiati nell’ambito informatico.
L’Insertion Sort è un algoritmo di ordinamento che funziona suddividendo l’array in due parti: una parte ordinata e una parte non ordinata. Inizia considerando l’elemento successivo nella parte non ordinata e lo inserisce nella parte ordinata, spostando gli elementi più grandi verso destra per fare spazio al nuovo elemento. Ecco come funziona passo dopo passo:
Supponiamo di avere l’array [5, 2, 4, 6, 1, 3]
e vogliamo ordinarlo con l’Insertion Sort. Procediamo a verificare passo per passo il funzionamento dell’Insertion Sort sull’array in questione:
- Iterazione 1:
- Elemento corrente:
2
- Confronto con gli elementi ordinati a sinistra (
5
).5
è maggiore di2
, quindi5
viene spostato a destra per fare spazio a2
. - Array parzialmente ordinato:
[2, 5, 4, 6, 1, 3]
- Elemento corrente:
- Iterazione 2:
- Elemento corrente:
4
- Confronto con gli elementi ordinati a sinistra (
5
,2
).5
è maggiore di4
, quindi5
viene spostato a destra per fare spazio a4
. - Array parzialmente ordinato:
[2, 4, 5, 6, 1, 3]
- Elemento corrente:
- Iterazione 3:
- Elemento corrente:
6
- Non ci sono elementi più piccoli a sinistra di
6
, quindi rimane nella sua posizione attuale. - Array parzialmente ordinato:
[2, 4, 5, 6, 1, 3]
- Elemento corrente:
- Iterazione 4:
- Elemento corrente:
1
- Confronto con gli elementi ordinati a sinistra (
6
,5
,4
,2
). Tutti questi sono maggiori di1
, quindi vengono spostati a destra per fare spazio a1
. - Array parzialmente ordinato:
[1, 2, 4, 5, 6, 3]
- Elemento corrente:
- Iterazione 5:
- Elemento corrente:
3
- Confronto con gli elementi ordinati a sinistra (
6
,5
). Sono maggiori di3
, quindi vengono spostati a destra per fare spazio a3
. - Array ordinato:
[1, 2, 3, 4, 5, 6]
- Elemento corrente:
Dopo queste iterazioni, l’array risulta completamente ordinato. La sequenza di operazioni eseguite corrisponde alla logica dell’Insertion Sort, dove gli elementi vengono inseriti uno per uno nella parte ordinata dell’array.
Programma Python per l’ordinamento per inserzione
La funzione insertionSort prende in input un array arr. Per prima cosa calcola la lunghezza dell’array (n). Se la lunghezza è 0 o 1, la funzione ritorna immediatamente perché un array con 0 o 1 elemento è considerato già ordinato.
Per gli array con più di un elemento, la funzione procede all’iterazione dell’array a partire dal secondo elemento. Prende l’elemento corrente (denominato “chiave”) e lo confronta con gli elementi della porzione ordinata dell’array che lo precedono. Se la chiave è più piccola di un elemento della porzione ordinata, la funzione sposta l’elemento a destra, creando spazio per la chiave. Questo processo continua finché non viene trovata la posizione corretta per la chiave, che viene quindi inserita in quella posizione.
L’esempio fornito mostra il processo di ordinamento con l’algoritmo insertion sort. L’array iniziale [12, 11, 13, 5, 6] viene sottoposto alla funzione insertionSort. Dopo l’ordinamento, l’array dovrebbe essere [5, 6, 11, 12, 13]. Il codice stampa l’array ordinato come output finale.
def insertionSort(arr): n = len(arr) # Get the length of the array if n <= 1: arr[j+1] = arr[j] j -= 1 arr[j+1] = key # test arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)
Versione ottimizzata dell’Insertion Sort
Esiste una interessante alternativa la cui paternità viene attribuita all’informatico Jon Louis Bentley: un insertion sort con sole tre righe di codice, molto intuitivo ed altrettanto facile da ricordare. È stato presentato e discusso all’interno del libro dell’autore Programming Pearls. Lo proponiamo in pseudo codice in quanto può essere facilmente tradotto e codificato nei vari linguaggi di programmazione.
for i = [1, n) for j = i; j>0 && x[j-1] > x[j]; j-- scambia(j-1, j)
L’algoritmo in questione prevede una funzione di scambio che funziona, come al solito in questi casi, con una variabile di appoggio tmp;
Usa il codice
189ed7ca010140fc2065b06e3802bcd5
per ricevere 5 € dopo l'iscrizione
scambia(a,b){ tmp = a; a = b; b = tmp; }
👇 Contenuti da non perdere 👇
- Lavoro 🔧
- Marketing & SEO 🌪
- Mondo Apple 🍎
- monitoraggio servizi online 📈
- Programmare 🖥
- Sicurezza & Privacy 👁
- Svago 🎈
- WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🔴 Che cos’è Omegle (guida e suggerimenti)
- 🔵 Cos’è lo scrapbooking
- 🔵 Errore HTTP 411 Length Required: come risolverlo e da cosa dipende