=== Imparando.net ===

Insertion sort adattativo

Questa versione dell'insertion sort è una versione migliorata della versione non adattativa, in quanto sfrutta tre diverse idee per migliorare i tempi di esecuzione pur rimanendo di tipo quadratico. Le tre idee sono:

  • Ad ogni passaggio, il nuovo elemento aggiunto nel vettore ordinato, ferma i controlli appena trova un elemento minore di sè stesso, poichè tutti gli ulteriori controlli non avrebbero nessun effetto.
  • Non vengono fatti degli scambi, ma semplicemente gli elementi vengono fatti "scorrere" verso il basso, in quanto gli scambi comportano ogni volta due operazioni inutili.
  • Viene fatto un primo passaggio di bubble sort sul vettore per mettere il minimo in testa, in modo da eliminare il controllo esplicito sullo sforamento dell'indice 0, che avverrebbe quando si tentasse di mettere in posizione l'elemento più piccolo dell'insieme. Questo elemento viene in generale chiamato "sentinella" e può evitare di far usare dei controlli espliciti.

Filmato che mostra il funzionamento dell'insertion sort adattativo attraverso una simpatica danza: rispetto all'algoritmo implementato nel codice sottostante, qui i ballerini eseguono un numero di scambi superiore, poichè non si limitano a far scorrere gli elementi verso il basso, ma effettuano ogni volta uno scambio.


Sorgenti ...

download-icon Main.cpp

Altro ...

download_icon Main.html