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, quindi5viene 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, quindi5viene 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;
scambia(a,b){
tmp = a;
a = b;
b = tmp;
}
👇 Da non perdere 👇
- 📈 Analizza Cellulari 📱
- 🔐 AI che dolor, Chat 🏴
- 🎯 Targetizza Database SQL 🗄
- 📊 Analizza Errori più comuni 📛
- 🚧 Costruisci Evergreen 📟
- 👩💻 Programma Gratis 🎉
- 💻 Configura Hosting a confronto 💑
- 🔒 Conosci Hosting reti e domini 💻
- 👩💻 Tapioca Informatica 🖥
- 💻 Iconizza Internet 💻
- 🔒 Gestisci Lavoro 🔧
- 💡 Mostra Marketing & SEO 🌪
- 🔑 Apprendi Meteo ⛅
- 🤯 Visiona Mondo Apple 🍎
- 🔍 Supervisiona Mondo Domini 🌐
- 🚀 Metti in cloud monitoraggio servizi online 📈
- 🔮 Anatomizza Nuove tecnologie 🖥
- 🔒 Antani PEC e firma digitale 📩
- 👀 Prematura Programmare 🖥
- 🎮 Lonfa Scrivere 🖋
- 🔒 Conosci Servizi di SMS 📶
- 👀 Guarda Sicurezza informatica e privacy digitale 🖥
- 🎮 Ricorda Siti web 🌎
- 🤖 Ottimizza Spiegoni artificiali 🎓
- 🧠 Neuralizza Svago 🎈
- 📡 Quantizza Usare Excel 🌀
- 🤖 Sovrascrivi Windows 😲
- 🎨 Personalizza Wireless 🚁
- 🔑 Decifra WordPress 🤵
- 💬 Il nostro canale Telegram: iscriviti
- 🟠 ARPANET: perchè internet (NON) è nato con scopi militari
- 🟡 Che vuol dire loading
- 🔵 WordPress: 6 modi per migliorare le prestazioni (senza installare plugin)
