Selection sort: differenze tra le versioni

Versione delle 09:44, 12 gen 2012

Versione delle 14:00, 24 gen 2012

Riga 29:

A livello asintotico viene studiato il tempo di esecuzione dei due cicli for.

<math>\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} c </math>, dove ''c'' è una costante, dato che l'operazione effettuata può essere rappresentata da una costante.

<math>\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} 1 = \sum_{i=1}^{n-1} (n - i + 1) = \sum_{i=1}^{n-1} (n - 1) - \sum_{i=1}^{n-1} i \approx n^2 - \frac{n(n + 1)}{2} \approx \frac{n^2}{2} = \theta(n^2) </math>

L'ordinamento per selezione effettua <math>N(N-1)/2</math> confronti e, nel caso peggiore/migliore/medio, <math>\theta(n-1)</math> scambi.