Insertion sort
Insertion sort è un esperimento interattivo di Algoritmi in azione, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
L’insertion sort funziona come ordinare le carte in mano: la parte sinistra è già ordinata e ogni nuovo elemento (key) si sposta a sinistra finché non incontra uno più piccolo. Gli elementi più grandi scorrono di un posto a destra. Su dati casuali è O(n²), ma su dati quasi ordinati quasi O(n): un array ordinato richiede solo n−1 confronti.
Prova questo: Eseguilo su un array quasi ordinato e poi su uno invertito. Quante volte più spostamenti servono a quello invertito?
Domande frequenti
Che cosa mostra l’esperimento «Insertion sort»?
L’insertion sort funziona come ordinare le carte in mano: la parte sinistra è già ordinata e ogni nuovo elemento (key) si sposta a sinistra finché non incontra uno più piccolo. Gli elementi più grandi scorrono di un posto a destra. Su dati casuali è O(n²), ma su dati quasi ordinati quasi O(n): un array ordinato richiede solo n−1 confronti.
Come provo «Insertion sort»?
Eseguilo su un array quasi ordinato e poi su uno invertito. Quante volte più spostamenti servono a quello invertito?
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.