Migliore risposta
Prima di tutto, ci si dovrebbe chiedere perché usare un algoritmo di ordinamento quadratico quando esistono alternative asintoticamente più veloci, come il mergesort o quicksort. Per array piccoli (meno di 20-30 elementi), sia lordinamento per inserzione che lordinamento per selezione sono in genere più veloci delle alternative O (n * logn). In effetti, molti algoritmi di ordinamento basati sul paradigma divide et impera passano allordinamento per inserzione o allordinamento per selezione quando larray è abbastanza piccolo.
Tra lordinamento per inserzione e lordinamento per selezione, quando usare quale?
Di solito, lordinamento per inserzione eseguirà meno confronti rispetto allordinamento per selezione, a seconda del grado di “ordinamento” dellarray. Mentre lordinamento per selezione deve scansionare le parti rimanenti dellarray quando si inserisce un elemento, lordinamento per inserzione scansiona solo gli elementi necessari. Ciò significa che quando larray è già ordinato o quasi, lordinamento per inserzione viene eseguito in tempo O (n).
Un vantaggio dellordinamento per selezione rispetto allordinamento per inserzione, è che il numero di scritture (scambi) è in O (n), mentre nellordinamento per inserzione è in O (n ^ 2). Questo può essere importante se stai ordinando sulla memoria Flash, ad esempio, perché le scritture riducono la durata della memoria Flash.
Risposta
In un ordinamento di selezione, per ogni elemento che deve essere aggiunto alla sezione ordinata, devi scansionare la intera parte non ordinata dellelenco per trovare lelemento minimo rimanente. In un ordinamento per inserzione, devi cercare la sezione ordinata per scoprire dove va lelemento successivo ma la ricerca termina una volta trovato il punto di inserimento (circa la metà attraverso la sezione ordinata in media).
Quindi lordinamento per selezione richiede in media N / 2 confronti per ogni elemento da aggiungere alla sezione ordinata e lordinamento per inserzione richiede in media N / 4 confronti. Tuttavia, lordinamento per inserzione ha unulteriore penalità di tempo durante lordinamento di un array. Ciascuno dei confronti N / 4 (in media) richiede che lelemento sia spostato verso lalto, quindi ci sono anche N / 4 mosse e confronti. Lordinamento della selezione richiede solo un singolo scambio.
In generale, lordinamento per inserzione di solito vince la gara. Ciò è particolarmente vero se ci sono funzioni veloci di “spostamento dei blocchi” in giro (per gli array).