La séquence précédente portait sur l’étude comparative des algorithmes de tri à coût quadratique. Rappelons qu’un coût quadratique est en ${\tt O\big(n^2\big)}$ et signifie qu’un doublement de la dimension de l’objet à traiter multiplie par 4 le nombre d’opérations c’est à dire le temps de traitement (${\tt n}$ est la taille du tableau). Cette nouvelle séquence a pour objectif l’étude de deux algorithmes de tri à coût quasi-linéaire soit en ${\tt O\big(n\ln(n)\big)}$.
Les courbes suivantes permettent de visualiser la différence de comportement entre ${\tt n^2}$ et ${\tt n\ln(n)}$.
from matplotlib.pyplot import plot, clf, show, legend, rcParams
from math import log
from time import time
rcParams['text.usetex'] = True # pour afficher des symboles mathématiques avec Latex (dans la légende)
clf() # on efface la figure (si on en avait déjà affiché une)
X = [] # abscisses
Y = [] # ordonnées
Y2 = [] # ordonnées
for k in range(10,210,10): # k va de 10 à 200 par pas de 10
X.append(k)
Y.append(k**2)
Y2.append(k*log(k))
plot(X, Y, label='courbe de $n\longmapsto n^2$', marker='+', markersize=10, linewidth=2, color ='r')
plot(X, Y2, label='courbe de $n\longmapsto n*\ln(n)$', marker='+', markersize=10, linewidth=2, color ='g')
legend()
show()
Rappelons qu'il existe deux syntaxes possibles pour échanger la valeur de deux variables ${\tt a}$ et ${\tt b}$.
a = 1234
b = 6789
a = b
b = a
print(a, b) # ECHEC de l'échange
6789 6789
a = 1234
b = 6789
x = a # on mémorise la valeur de a dans une variable auxiliaire
a = b # la valeur de a est écrasée par la valeur de b
b = x # on récupère l'ancienne valeur de a grâce à la variable x
print(a, b) # cette méthode est valable avec n'importe quel langage de programmation
6789 1234
a = 1234
b = 6789
a, b = b, a # affectation simultanée: Python évalue le membre de droite et l'affecte au membre de gauche
print(a, b) # cette méthode élégante est valable uniquement avec le langage Python
6789 1234
Pour échanger deux valeurs dans une liste Python la syntaxe est la même. Par exemple pour échanger la première et la cinquième valeur:
L = [ 2*k+1 for k in range(10 )] # liste définie par compréhension
print(L) # liste des 10 premiers entiers impairs
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
On échange ${\tt L[0]}$ et ${\tt L[4]}$.
x = L[0]
L[0] = L[4]
L[4] = x
print(L)
[9, 3, 5, 7, 1, 11, 13, 15, 17, 19]
Ou plus simplement:
L[0], L[4] = L[4], L[0]
print(L) # on fait deux fois le même échange donc les éléments ont repris leur place
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Rappelons le principe du tri par insertion.
def triselection(T):
n = len(T)
for i in range(n-1):
# calcul de l'indice où se trouve le minimum de la liste [ T[i], T[i+1], ... , T[n-1] ]
indMin = i
for j in range(i+1, n):
if T[j] < T[indMin]:
indMin = j
# ici on sait que le minimum est en indice indMin
# on l'échange avec l'élément donc l'indice est i
T[i], T[indMin] = T[indMin], T[i] # affectation simultanée
Cette fonction modifie la liste ${\tt T}$ en place: aucune autre liste n'est utilisée et c'est la liste initiale qui est modifiée (et donc pas besion de renvoyer une nouvelle liste en sortie avec ${\tt return}$).
On peut veut proposer une version récursive de cet algorithme: elle va créer en mémoire de nombreuses listes lors des appels récursifs, mais elle sera beaucoup plus élégante à lire.
Pour cela on rappelle que si ${\tt T}$ est une liste on obtient la même liste privée de ${\tt T[indMin]}$ avec la syntaxe ${\tt T[\;:indMin\,]+T[\,indMin+1:\;]}$
La close d'arrêt est donnée par les listes vides ou de taille $1$. Pour une liste de taille quelconque on met son élément minimum en première position et on la concatène avec la liste restant triée récursivement.
Q1. Compléter le code suivant:
def TriSelectionRecursif(L):
if len(L) <= 1: # close d'arrêt: liste vide ou à un seul élément
return ............
else:
n = len(L)
# on calcule l'indice indMin du minimum de L
indMin = .........
for j in range( ... , ... ):
if ......... :
.........
# on renvoie la liste commençant par L[indMin]
# suivi de la liste L privée de L[indMin] triée récursivement
return .................. # appel récursif
# Cellule pour tester
L = [3, 5, 2, 6, 4, 1, 8]
L2 = TriSelectionRecursif(L)
print(L2)
On note ${\tt c_n}$ le nombre de comparaisons effectués par l'algorithme récursif dans le pire des cas, pour une liste de taille ${\tt n}$.
Q4. Justifier que ${\tt c_{n}\leq c_{n-1}+n-1}$. En déduire que ${\tt c_n=O(n^2)}$.
On retrouve donc la même complexité que pour la version itérative implémentée à la séance précédente.
Les "tableaux" sont manipulés sous forme de listes Python.
On choisit dans la liste ${\tt L}$ un élément particulier (en général le premier), appelé pivot: ${\tt pivot = L[0]}$.
On crée alors deux sous-tableaux : ${\tt Linf}$ contenant les éléments strictement inférieurs à ${\tt pivot}$, et ${\tt Lsup}$ contenant les éléments supérieurs ou égaux à ${\tt x}$.
Par exemple: avec ${\tt L = [8, 1, 5, 14, 4, 15, 12, 6, 2, 11, 10, 7, 9]}$ on choisit comme pivot ${\tt pivot = 8}$ et on construit ${\tt Linf}$ et ${\tt Lsup}$:
On relance le tri de manière récursive sur ces deux listes qui deviennent donc des listes triées:
On n'a pas à s'occuper de comment elles ont été triées: c'est la magie de la récursivité! 🪄 🪄
${\tt LinfTri}$ est constituée des éléments ${\tt < pivot}$ et ${\tt LsupTri}$ est constituée des éléments ${\tt \geq pivot}$, on obtient donc simpement la liste initiale sous forme triée en ajoutant ${\tt pivot}$ à la fin de ${\tt LinfTri}$ puis en concaténant avec ${\tt LsupTri}$:
Cet algorithme est un exemple d’une méthode générale utilisée en récursivité, appelée diviser pour régner: on divise le problème initial en deux sous-problèmes qu’on sait résoudre, et on revient ensuite au problème initial.
Dans le cas du tri rapide, les appels récursifs sont lancés jusqu’à tomber sur des listes de taille 1 ou 0, qui sont déjà triées (ce sont les closes d'arrêt), et il ne reste plus qu’à les concaténer dans le bon ordre.
Voici une réprésentation des appels récursifs:
Une fois la liste découpée en sous-listes de taille $1$ dans la pile d'appels, les morceaux sont recollés dans le bon ordre pour avoir un tri de la liste initiale.
Q3. Compléter le code suivant:
def TriRapideRecursif(L):
if len(L) <= 1: # close d'arrêt
return L
else:
pivot = .........
Linf = []
Lsup = []
for x in ......... : # on parcourt une liste mais laquelle ?
if ......... :
Linf.append(x)
else:
Lsup.append(x)
return .................. + ......... + .................. # appels récursifs
# Cellule pour tester
L = [3, 5, 2, 6, 4, 1, 8]
L2 = TriRapideRecursif(L)
print(L2)
On note ${\tt c_n}$ la complexité de l'algorithme récursif dans le pire des cas, pour une liste de taille ${\tt n}$.
Q4. Justifier que ${\tt c_{n}\leq c_{n-1}+n-1}$. En déduire que ${\tt c_n=O(n^2)}$.
C'est encore une complexité quadratique. En théorie ce n'est donc pas mieux que le tri par sélection.
On va évaluer empiriquement la vitesse des deux fonctions précédentes.
Q5. Comprendre puis exécuter les instructions suivantes.
from matplotlib.pyplot import plot, clf, show, legend
from random import randint
from time import time
clf() # on efface la figure (si on en avait déjà affiché une)
X = [] # abscisses
Y = [] # ordonnées
Y2 = [] # ordonnées
for k in range(10,210,10): # k va de 10 à 200 par pas de 10
X.append(k)
L = [ randint( -100000, 10000) for i in range(k) ] # liste aléatoire de k entiers
LL = L[:] # copie de L dans LL ( pourquoi LL = L ne fonctionne pas ?? )
debut = time()
TriSelectionRecursif(L)
fin = time()
duree = fin - debut
Y.append(duree)
debut = time()
TriRapideRecursif(LL)
fin = time()
duree = fin - debut
Y2.append(duree)
plot(X, Y, label='tri selection', marker='+', markersize=10, linewidth=2, color ='r')
plot(X, Y2, label='tri rapide', marker='+', markersize=10, linewidth=2, color ='g')
legend()
show()
La victoire du tri rapide est écrasante! On peut en effet montrer que la complexité observée empiriquement (notion hors-programme) est en ${\tt O\big(n\ln(n)\big)}$.
Nous allons encore créer un programme récursif utilisant la méthode « diviser pour régner ».
Pour le tri rapide, l’idée était de faire en sorte que les deux parties à concaténer donnent directement le tableau trié, le défaut étant qu’on ne coupe pas toujours en deux parties égales (d'où la complexité en ${\tt O(n^2)}$).
Pour le tri fusion, le principe est différent. On coupe le tableau en deux morceaux toujours égaux, qu’on trie, puis reste l’étape délicate appelée fusion: elle consiste à fusionner ces deux tableaux triés en un tableau encore trié (ce n'est donc plus une simple concaténation).
La fonction principale est la fonction ${\tt fusion}$ qui permet de « fusionner » deux tableaux triés en un tableau trié. Pour cela on procède manière récursive : le plus petit élément des deux tableaux est placé en première position du nouveau tableau, il reste ensuite à fusionner les deux tableaux privés de cet élément.
Noter que comme les deux tableaux sont triés, leur plus petit élément est en première position, il n'y a donc pas besoin de le rechercher dans tout le tableau.
Q6. Compléter le code suivant:
def Fusion(L1, L2):
if len(L1) == 0:
return .........
elif len(L2) == 0:
return .........
else:
if ......... :
return ..................
else:
return ..................
# Cellule pour tester
L1 = [2,4,6,8]
L2 = [1,3,5,7]
L3 = Fusion(L1,L2)
print(L3)
Pour trier une liste ${\tt L}$ de taille ${\tt n = len(L)}$ on va donc trier récursivement ses deux moitiés ${\tt L[:n//2]}$ et ${\tt L[n//2:]}$ puis les fusionner.
Q7. En utilisant la fonction ${\tt Fusion(L1,L2)}$ écrire une fonction récursive ${\tt TriRapideRécursif(L)}$ qui renvoie une version triée de la liste ${\tt L}$.
def TriFusionRecursif(L):
if len(L) <= 1:
return .........
else:
n = len(L)
return ..................
# Cellule pour tester:
L = [38, 27, 43, 3, 9, 82, 10]
L2 = TriFusionRecursif(L)
print(L2)
Si on note ${\tt c_n}$ la complexité de l'algorithme récursif dans le pire des cas, pour une liste de taille ${\tt n}$, on a ${\tt c_n\leq 2c_{\lfloor n/2\rfloor}}$ et on peut montrer que ${\tt c_n=O\big(n\ln(n)\big)}$.
C'est cette fois une complexité quasi-linéaire. En théorie c'est donc le meilleur algorithme de tri.
Pour le confirmer ou l'infirmer, on compare empiriquement les trois algorithmes.
Q8. Comprendre puis exécuter les instructions suivantes. Commenter les trois courbes obtenues.
from matplotlib.pyplot import plot, clf, show, legend
from random import randint
from time import time
clf() # on efface la figure (si on en avait déjà affiché une)
X = [] # abscisses
Y = [] # ordonnées
Y2 = [] # ordonnées
Y3 = [] # ordonnées
for k in range(10,510,10): # k va de 10 à 500 par pas de 10
X.append(k)
L = [ randint( -100000, 10000) for i in range(k) ] # liste aléatoire de k entiers
LL = L[:] # copie de L dans LL ( pourquoi LL = L ne fonctionne pas ?? )
LLL = L[:] # copie de L dans LLL
debut = time()
TriSelectionRecursif(L)
fin = time()
duree = fin - debut
Y.append(duree)
debut = time()
TriRapideRecursif(LL)
fin = time()
duree = fin - debut
Y2.append(duree)
debut = time()
TriFusionRecursif(LLL)
fin = time()
duree = fin - debut
Y3.append(duree)
plot(X, Y, label='tri selection', marker='+', markersize=10, linewidth=2, color ='r')
plot(X, Y2, label='tri rapide', marker='+', markersize=10, linewidth=2, color ='g')
plot(X, Y3, label='tri fusion', marker='+', markersize=10, linewidth=2, color ='b')
legend()
show()