Tri par sélection python : Implémentation de l’algorithme exemple complet avec code source.
tab = [111, 34, 22, 55, 4, 2, 1, 77] for i in range(0,len(tab)-1): min = i for j in range(i+1,len(tab)): if tab[j]<tab[min]: min = j if (min != i): tmp = tab[i] tab[i] = tab[min] tab[min] = tmp print(tab)
Introduction :
Si on considère l’opération de comparaison « if tab[j]<tab[min] » et n la taille du tableau.
Si i = 0 ==> (n-1) comparaisons
Si i = 1 ==> (n-2) comparaisons
… Si i = n-2 ==> 1 comparaison
soit n * (n-1) comparaisons
Donc la boucle for i in range(0,len(tab)-1): s’exécute n-1 fois
La boucle for j in range(i+1,len(tab)): s’exécute (n-(i+1) + 1) fois
La complexité en nombre de comparaison est égale à la somme des n-1 termes suivants (i = 1, …i = n-1)
C = (n-2)+1 + (n-3)+1 +…..+1+0 = (n-1)+(n-2)+…+1 = n.(n-1)/2 (c’est la somme des n-1 premiers entiers).
La complexité en nombre de comparaison est de de l’ordre de n², on écrit O(n²).
Tri par sélection python liens externes :
https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins