Selection sort: differenze tra le versioni

Versione delle 21:10, 15 mag 2012

Versione delle 17:08, 17 ott 2012

Riga 31:

<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.