Blog

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:

1. Iterazione 1:
   • Elemento corrente: 2
   • Confronto con gli elementi ordinati a sinistra (5). 5 è maggiore di 2, quindi 5 viene spostato a destra per fare spazio a 2.
   • Array parzialmente ordinato: [2, 5, 4, 6, 1, 3]
2. Iterazione 2:
   • Elemento corrente: 4
   • Confronto con gli elementi ordinati a sinistra (5, 2). 5 è maggiore di 4, quindi 5 viene spostato a destra per fare spazio a 4.
   • Array parzialmente ordinato: [2, 4, 5, 6, 1, 3]
3. 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]
4. Iterazione 4:
   • Elemento corrente: 1
   • Confronto con gli elementi ordinati a sinistra (6, 5, 4, 2). Tutti questi sono maggiori di 1, quindi vengono spostati a destra per fare spazio a 1.
   • Array parzialmente ordinato: [1, 2, 4, 5, 6, 3]
5. Iterazione 5:
   • Elemento corrente: 3
   • Confronto con gli elementi ordinati a sinistra (6, 5). Sono maggiori di 3, quindi vengono spostati a destra per fare spazio a 3.
   • Array ordinato: [1, 2, 3, 4, 5, 6]

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;
}

👇 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

Numero di visualizzazioni (dal 21 agosto 2024): 4

Pubblicità - Continua a leggere sotto :-)

Seguici su Telegram: @trovalost