Le tri par insertion en Python en moins de 128 mots

Le tri par insertion est un tri lent, stable, en place (on travaille sur la structure directement et pas une copie).

Le tri par insertion est comparable au tri que l’on effectue d ‘un jeu de carte. 

def tri_par_insertion(tableau):
	#parcours de tout les elements du tableau
	global nombre_operation
	for i in range(1,len(tab)-1):
		#pour chacun des elements du tableau on parcours les precedent et on echange
		#on sauvegarde la valeur de l'element courant
		valeurElementCourant = tableau[i]
		print("element courant : " + str(tableau[i]) + " - indice i=" + str(i))
		j = i
		#on definit l'indice j et on parcours les elements predents tant qu'il '
		while(j>0 and tableau[j-1]>valeurElementCourant):
			#si l'element parcouru parmi les valeurs precedente est superieur a l'element courant on l'insere à sa place et on decale a gauche
			tableau[j] = tableau[j-1]
			j -= 1
			nombre_operation +=1
		#lorsqu'on sort de la boucle on a place tout les elements superieur a l'element courant a droite de j il faut alors mettre l'element courant à la position j
						
	tableau[j] = valeurElementCourant
		
nombre_operation = 0
tab = [3,9,6,1,2,4,7,5,8]
print("avant tri par insertion : " + str(tab))
tri_par_insertion(tab)
print("apres tri par insertion : " + str(tab))
print("nombre d'operation : " + str(nombre_operation))