Tri par sélection Python – Implémentation de l’algorithme

Tri par sélection python : Implémentation de l’algorithme exemple complet avec code source.

tri par sélection python
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

https://www.python.org/

Liens internes :

https://128mots.com/index.php/category/python/