ORDINAMENTO INGENUO (Insertion Sort)

ALGORITMO:



SPIEGAZIONE ALGORTIMO

Nella prima esecuzione del ciclo interno, per j=1, si confronta il primo elemento con tutti gli altri, scambiando il valore dei due elementi se a[1]>a[i]. In questo modo, al termine del ciclo a[1] conterrà l’elemento più piccolo. Alla seconda iterazione del ciclo esterno si ripete la stessa procedura: alla fine a[2] conterrà il secondo valore in ordine di grandezza. Quando termina tutto il ciclo esterno il vettore risulterà ordinato.

COMPLESSITA’
Osserviamo che per j=1 l’istruzione del ciclo interno, il confronto fra a[j] e a[i], viene eseguita (n-1) volte, (n-2) volte per j=2, (n-3) volte per j=3 e così via fino a j=(n-1).
Il numero di confronti effettuati è quindi pari a (n-1)+(n-2)+(n-3)+…+2+1 = \frac{n(n-1)}{2} , che si rifà alla formula di Gauss: \sum_{k=1}^n k = \frac{n(n-1)}{2}

Questo algoritmo ha quindi una complessità O(n^2).

---

Torna a Programmazione e Lab.