Considera un inserimento Ordina con un Sentinel su n valori, dove ogni valore si verifica esattamente due volte nell'input (quindi n deve essere pari). Quindi l'input migliore per i confronti è quando gli elementi sono già ordinati e il numero esatto di confronti nel caso migliore è n-1. Credo che l'input peggiore per i confronti sia quando gli elementi sono ordinati in ordine inverso. Ma qual è il numero esatto di confronti in questo caso? e perché?
Per prima cosa, esaminiamo il caso migliore. Hai n elementi. Il primo che si salta perché non c'è niente prima di confrontarsi, quindi ci sono solo elementi n-1 che potrebbero dover essere spostati. Se un elemento non ha bisogno di essere spostato a sinistra, allora lo impariamo dopo un solo confronto. Quindi se nessun elemento deve essere spostato a sinistra (perché la matrice è già ordinata), allora sono necessari solo 1 volte i confronti n-1, quindi n-1 totale.
Ora, se l'array è ordinato in ordine inverso, significa che ogni elemento deve essere spostato fino all'estremità sinistra dell'array. Saltiamo il 1 ° elemento come al solito, quindi 0 confronti lì. Il 2 ° elemento si muove 1 volta dopo 1 confronto, il 3 ° elemento si muove 2 volte dopo 2 confronti, il 4 ° elemento si muove 3 volte dopo 3 confronti ... e così via. L'ennesimo elemento richiede sempre confronti n-1 per spostarsi completamente a sinistra. Quindi il numero totale di confronti per tutti gli n elementi è 0 + 1 + 2 + 3 + ... + n-1, che le formule di sommatoria ci dicono è (n-1) ((n-1) +1) / 2 = (n-1) (n / 2) confronti , o in alternativa O (n ^ 2).
Hai ragione nel ritenere che questo scenario sia il caso peggiore per l'ordinamento degli inserimenti. Il ciclo esterno dell'algoritmo non può mai avere più di n iterazioni e il ciclo interno di ith non può mai avere più di iterazioni perché decrementiamo ogni volta j, quindi ti ritroverai con 0 + 1 + 2 + 3 + ... + n- 1 come il numero massimo possibile di iterazioni del ciclo interno per l'intero algoritmo (e l'unico confronto a cui teniamo è quello eseguito da un'iterazione del ciclo interno). Potremmo anche provare a delineare una prova che questo è l'unico scenario peggiore per l'ordinamento degli inserimenti, ma per ora lo lascerò come esercizio.
Leggi altre domande sui tag algorithms algorithm-analysis