for ( i = 1 ; i <= N ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;
for ( k = i ; k > j ; k-- )
arr[k] = arr[k - 1] ;
arr[k + 1] = temp ;
}
}
}
Fonte: link
In caso contrario, si può davvero chiamare insertion sort? Questa versione di ordinamento è presente in un libro dell'autore reputato originariamente.
Il caso migliore si verifica quando l'istruzione if non viene mai inserita. Quindi dobbiamo contare il numero di volte in cui valutiamo la condizione dell'istruzione if per determinare che non vogliamo farlo.
Il ciclo esterno varia da 1 a N e le gamme interne j da 0 a i. Contiamo il numero di volte che controlliamo che la condizione if:
At i = 1 we look at j 1 times (at j = 0)
At i = 2 we look at j 2 times (at j = 0, 1)
At i = 3 we look at j 3 times (at j - 0, 1, 2)
At i = 4 we look at j 4 times (at j - 0, 1, 2, 3)
At i = 5 we look at j 5 times
At i = N-1 we look at j N times (at j - 0, 1, 2, ... N-1)
Questa è la classica serie aritmetica 1 + 2 + 3 + 4 + .... + N conosciuta come O (N ^ 2).
Non è un tipo di inserimento. L'ordinamento per inserimento reale è O (N) nel migliore dei casi.
Non so cosa sia questo algoritmo.
Supponendo che sia già stato ordinato, quell'istruzione if non viene mai inserita. Quindi hai due loop in tutto e verrà eseguito in n ^ 2 volta.
Ma non è "Big-O". Big-O si preoccupa del momento peggiore, non il migliore. Credo che questo algoritmo sia O (n ^ 3). I loop interni eseguono solo n / 2 e ... penso n / 3, ma tutta questa divisione viene gettata via quando si parla di Big-O.
È passato un po 'di tempo, ma penso che lo scenario migliore si chiami "grande omega".
Leggi altre domande sui tag sorting algorithm-analysis