Confronti
Scambi
Passata

  • In inserimento
  • Confrontate
  • Scambiate
  • Parte ordinata

Scopri di più sull'insertion sort

Insertion sort

L'insertion sort (ordinamento per inserimento) funziona come molte persone ordinano le carte che hanno in mano. Mantiene una parte ordinata all'inizio della lista, prende il valore successivo e lo fa scorrere indietro oltre ogni valore più grande finché non trova posto. Avvia l'ordinamento a qualsiasi velocità, oppure procedi un confronto alla volta, e guarda i contatori di confronti, scambi e passate. Premi Avvia per guardare l'ordinamento, oppure Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. I riquadri contano confronti, scambi e passate. Scegli quante barre usare, come partono, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scegli quante barre usare e come partono: casuali, quasi ordinate, in ordine inverso o con pochi valori distinti. Oppure inserisci i tuoi numeri.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto dell'ordinamento.
  3. Prova una lista quasi ordinata e una inversa, e confronta quanti confronti richiede ciascuna.

Come funziona l'insertion sort

Il primo valore da solo è una parte ordinata. Prendi il secondo valore e confrontalo con quello prima; se quello è più grande, scambiali, e continua a confrontare e scambiare finché il valore prima non è più grande o il valore arriva in testa. Ora i primi due valori sono in ordine. Fai lo stesso con il terzo valore, il quarto e così via fino alla fine della lista.

Veloce sulle liste quasi ordinate

Ogni passata si ferma al primo valore non più grande, quindi un valore già vicino al suo posto costa solo un confronto o due. Una lista ordinata richiede n − 1 confronti e nessuno scambio; una lista inversa, il caso peggiore, ne richiede n(n − 1)/2 di ciascun tipo. Il numero di scambi è sempre uguale al numero di inversioni nella lista iniziale, cioè le coppie fuori ordine. Per questo l'insertion sort si usa spesso per liste brevi o quasi ordinate, e dentro ordinamenti più veloci per finire i pezzi piccoli.

Domande frequenti

Come funziona l'insertion sort?

Costruisce una parte ordinata all'inizio della lista. Ogni passata prende il valore successivo e lo sposta indietro oltre ogni valore più grande che lo precede, finché non trova posto. Dopo la passata k i primi k + 1 valori sono in ordine, anche se un valore successivo può ancora inserirsi tra loro.

Quanti confronti e scambi fa l'insertion sort?

Gli scambi sono sempre pari al numero di inversioni nella lista iniziale: nessuno per una lista ordinata, n(n − 1)/2 per una inversa. I confronti sono gli scambi più al massimo uno per passata, quindi tra n − 1 e n(n − 1)/2.

Perché l'insertion sort è veloce sulle liste quasi ordinate?

Perché una passata si ferma appena incontra un valore non più grande. Quando ogni valore è vicino al suo posto finale, ogni passata è breve, e l'intero ordinamento richiede un tempo vicino a n.

L'insertion sort è stabile?

Sì. Un valore supera solo valori strettamente più grandi, quindi i valori uguali non si superano mai e mantengono il loro ordine originale.

I miei numeri vengono inviati da qualche parte?

No. L'ordinamento avviene nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor