Lycée du Parc -Junier
Quelques sites internet avec des applications de simulations d'algorithmes de tris et des outils de visualisation :
cadeau.py
#imports de modules
import time
from random import randint, random
#Pour tester les fonctions de tri
#un tableau contenant 3 tableaux d'entiers aléatoires de tailles 10, 100, 1000
BENCH2 = [[randint(1, 2*10**i) for _ in range(10**i)] for i in range(1,4)]
#idem mais avec 3 tableaux d'entiers aléatoires de tailles impaires
BENCH1 = [[randint(1, 2*10**i) for _ in range(10**i + 1)] for i in range(1,4)]
def bontri(t):
'''Détermine si un tableau est trié dans l'ordre croissant'''
for k in range(len(t)-1):
if t[k] > t[k+1]:
return False
return True
def procedure_to_fonction(f):
'''Remplace la fonction f qui est une procedure ne retournant rien par une
fonction fbis qui exécute f sur ses arguments puis retourne ses arguments.
Nécessaire pour composer une fonction de tri sur place avec bontri'''
def fbis(*args):
f(*args)
return args
return fbis
def test_tri(tri, BENCH):
#copie profonde de BENCH qui est un tableau de tableaux
COPIE = [t[:] for t in BENCH]
return [bontri(procedure_to_fonction(tri)(t)) for t in COPIE]
def index_mini(t, debut):
if t == []:
return None
imini = debut
for j in range(debut+1, len(t)):
if t[j] < t[imini]:
imini = j
return imini
def tri_selection(t, verbose=False):
'''Tri sur place par sélection avec traçage des variables'''
if verbose:
template = "|{:^4}|{:^4}|{:^68}|"
print('-'*80)
print(template.format('i','j','t'))
print('-'*80)
for i in range(0, len(t)-1):
j = index_mini(t, i)
t[j], t[i] = t[i], t[j]
if verbose:
print(template.format(i,j,str(t)))
print('-'*80)
"""
>>> BENCH1[0]
[4, 17, 10, 8, 9, 6, 1, 1, 5, 4, 8]
>>> test_tri(tri_selection, BENCH1)
[True, True, True]
>>> BENCH1[0] #les tableaux du banc d'essai n'ont pas été modifiés
[4, 17, 10, 8, 9, 6, 1, 1, 5, 4, 8]
>>> tri_selection([5, 1, 6, 3], verbose=True) #traçage des variables
--------------------------------------------------------------------------------
| i | j | t |
--------------------------------------------------------------------------------
| 0 | 1 | [1, 5, 6, 3] |
--------------------------------------------------------------------------------
| 1 | 3 | [1, 3, 6, 5] |
--------------------------------------------------------------------------------
| 2 | 3 | [1, 3, 5, 6] |
--------------------------------------------------------------------------------
"""Analyse de complexité du tri par sélection pour un tableau de \(n\) entiers
index_mini(t, i) pour \(i\) allant de \(0\) à \(n-2\).index_mini(t, i) recherche le maximum dans la partie de \(n-i+1\) (index à partir de 0) valeurs non encore triées en effectuant \(n-i+1\) comparaisons.
def index_maxi(t, fin):
if t == []:
return None
imaxi = 0
for j in range(1, fin+1):
if t[j] > t[imaxi]:
imaxi = j
return imaxi
def tri_selection2(t):
for i in range(len(t)-1, 0, -1):
j = index_maxi(t, i)
t[j], t[i] = t[i], t[j]
"""
>>> test_tri(tri_selection2, BENCH2)
[True, True, True]
"""
def tri_insertion(t):
#Première boucle sur l'index du premier élément pas trié
for indexpastri in range(1, len(t)):
j = indexpastri - 1
#seconde boucle sur les éléments déjà triés
#pour insérer le premier élément pas trié parmi eux
while j >= 0 and t[j] > t[j+1]:
t[j], t[j+1] = t[j+1], t[j]
j = j - 1
def tri_insertion2(t):
'''Tri sur place par sélection en réduisant les affectations'''
for indexpastri in range(1, len(t)):
pastri = t[indexpastri]
j = indexpastri - 1
#tant qu'il reste des elements + grands à gauche
while j >= 0 and t[j] > pastri:
t[j+1] = t[j] #on décale vers la droite
j = j - 1 #on se déplace vers la gauche
t[j+1] = pastri #on insère l'élément pas trié
"""
>>> test_tri(tri_insertion, BENCH2)
[True, True, True]
>>> test_tri(tri_insertion2, BENCH2)
[True, True, True]
"""Analyse de complexité du tri par insertion :
def tri_bulle(t):
change = True
while change:
change = False
for i in range(len(t) - 1):
if t[i] > t[i + 1]:
t[i], t[i + 1] = t[i + 1], t[i]
change = True
def tri_bulle2(t):
'''Tri par bulle amélioré'''
change = True
#compteur de passages
c = 0
while change:
change = False
k = 0
#à chaque passage on doit balayer les positions de 0 à len(t) - 2
#moins les c dernières positions où sont déjà classés les + grands
#il reste donc len(t) - c positions à balayer
while k < len(t) - c:
if t[k] > t[k+1]:
t[k], t[k+1] = t[k+1], t[k]
# on modifie le booleen change uniquement au premier mouvement
if not change:
change = True
k += 1
c += 1
"""
>>> test_tri(tri_bulle, BENCH1)
[True, True, True]
>>> test_tri(tri_bulle2, BENCH1)
[True, True, True]
"""Analyse Complexité du tri par bulles :
Si le tableau est déjà trié dans l'ordre croissant, il n'y a aucune permutation d'éléments adjacents lors du premier passage. Le booleen change reste à False et la boucle while externe se termine au bout du premier tour. Il y a eu \(n-1\) comparaisons, il s'agit d'une complexité linéaire.
Si le tableau est trié dans l'ordre décroissant, lors de l'itération \(k\) de la boucle externe while (pour \(k\) allant de 1 à \(n\)), on fait remonter la plus grosse bulle non triée de la position 0 où elle est tombée après remontée des \(k-1\) bulles plus grosses, jusqu'à sa position finale \(n-k\). Lors de cette remontée, \(n-k\) comparaisons/permutations sont effectuées sauf pour le dernier passage. Pour \(k=1\) on a \(n-1\) comparaisons/permutations , pour \(k=2\) on a \(n-2\) comparaisons/permutations, pour \(k=n-1\) on a 1 comparaison et 1 permutation, pour \(k = n\) on a 1 comparaison et \(0\) permutation.
Au total, \(n-1 + n-2 + \cdots +1 + 1 = n(n-1)/2+1\)comparaisons sont effectuées. Il s'agit donc d'une complexité quadratique dans ce cas.