TP 6 : Programmation et complexité

1. Un tri simple : le tri à bulle

  1. Dans un premier temps, écrivez une fonction echange qui réalise l'échange de deux éléments adjacents: l'élément d'indice $i$ et celui d'indice $i+1$. Sur une liste L=[5, 9, 17, 18, 3, 2, 14, 8, 19, 13, 10] la fonction echange(L,4) retourne [5, 9, 17, 18, 2, 3, 14, 8, 19, 13, 10].
In [3]:
L=[5, 9, 17, 18, 3, 2, 14, 8, 19, 13, 10]
echange(L,4)
Out[3]:
[5, 9, 17, 18, 2, 3, 14, 8, 19, 13, 10]
In [1]:
#Question 1.1 

#Methode 1

def echange(L,n):
    for i in range(len(L)):
        if (i==n):
            temp = L[i]
            L[i] = L[i+1]
            L[i+1] = temp
    return L



L=[5, 9, 17, 18, 3, 2, 14, 8, 19, 13, 10]
echange(L,4)
Out[1]:
[5, 9, 17, 18, 2, 3, 14, 8, 19, 13, 10]
In [2]:
#Methode 2 , plus simple

def echange2(L,x):
    L[x],L[x+1] = L[x+1],L[x]
    return L

L=[5, 9, 17, 18, 3, 2, 14, 8, 19, 13, 10]
echange2(L,4)
Out[2]:
[5, 9, 17, 18, 2, 3, 14, 8, 19, 13, 10]
  1. Dans un deuxième temps implémentez le tri par bulle (triBulle) qui répète l'échange de deux éléments adjacents. Cet échange est répété autant de fois que la longueur de la liste (moins le nombre d'éléments qui ont été rangé à la bonne place, soit 1 par itération)
In [16]:
L=[6,3,4,2,5,1]
triBulle(L)

i= 0  j= 0 : [3, 6, 4, 2, 5, 1]
i= 0  j= 1 : [3, 4, 6, 2, 5, 1]
i= 0  j= 2 : [3, 4, 2, 6, 5, 1]
i= 0  j= 3 : [3, 4, 2, 5, 6, 1]
i= 0  j= 4 : [3, 4, 2, 5, 1, 6]
i= 1  j= 1 : [3, 2, 4, 5, 1, 6]
i= 1  j= 3 : [3, 2, 4, 1, 5, 6]
i= 2  j= 0 : [2, 3, 4, 1, 5, 6]
i= 2  j= 2 : [2, 3, 1, 4, 5, 6]
i= 3  j= 1 : [2, 1, 3, 4, 5, 6]
i= 4  j= 0 : [1, 2, 3, 4, 5, 6]
Out[16]:
[1, 2, 3, 4, 5, 6]
In [3]:
#Question 1.2

def triBulle(L):
    for i in range(len(L)):
        for j in range (len(L)): 
            if(L[i]<L[j]):  #compare les i aux j et lorsque L[i]<L[j],il y a échange entre L[i] et L[j] jusqu'à avoir
                temp=L[i]   #comparé tous les i avec tous les j dans la liste L
                L[i]=L[j]
                L[j]=temp  
    return L
        

L=[6,3,4,2,5,1]
triBulle(L)
Out[3]:
[1, 2, 3, 4, 5, 6]
In [4]:
#Methode 2 

def triBulle2(L):
    for i in range(len(L)-1):
        for j in range(len(L)-i-1):
            if L[j] > L[j+1]:
                echange(L,j)
    return L

L=[6,3,4,2,5,1]
triBulle2(L)
Out[4]:
[1, 2, 3, 4, 5, 6]
  1. Montrez expérimentalement que la complexité du tri à bulle est quadratique et trouvez les coefficients du polynôme de degré 2 qui correspond.
In [46]:
#Question 1.3 

import timeit
from functools import partial
import matplotlib.pyplot as plt
from random import randint
import numpy as np

#Etude éxpérimentale du tri à bulle

def listeAlea(n,max):
    return [randint(1,max) for i in range(n)]

x,y=[],[]
for i in range(10,2000,100):
    t=timeit.Timer(partial(triBulle,listeAlea(i,1000)))
    t=t.timeit(10)
    x.append(i)
    y.append(t)
    plt.plot(x,y)
    plt.title('Etude expérimentale du tri à bulle')
In [45]:
#Graphiquement on observe bien que la compléxité de la fonction tri à bulle est quadratique O(n²).

#Coefficient du polynôme de degré 2:
coefs=np.polyfit(x,y,2)
fit=np.poly1d(coefs)
print(fit)

           2
7.607e-07 x - 4.823e-05 x + 0.008073

2. Comparaison des algorithmes de tri

Le cours a rappelé le tri rapide, vous avez programmé le tri à bulle et Python implémente une fonction de tri (sort, déjà utilisée en TP). Sur un même jeu de données, comparez graphiquement la complexité de ces trois tris et essayez, pour chacun d'entre eux, de trouver une fonction d'approximation de la complexité.

In [7]:
#Question 2 

#Courbe du tri à bulle
x1,y1=[],[]
for i in range(1,1000,10):
    testTimer=timeit.Timer(partial(triBulle,listeAlea(i,1000)))
    t1=testTimer.timeit(number=10)
    x1.append(i)
    y1.append(t1)

#Courbe du tri d'une liste aleatoire
x2,y2=[],[]
for i in range(1,1000,10):
    testTimer=timeit.Timer(partial(sorted,listeAlea(i,1000)))
    t2=testTimer.timeit(number=10)
    x2.append(i)
    y2.append(t2)

#Tri rapide d'une liste
def quicksort(L):
    if L==[] : return []
    else :
        p=L[0]
        L1 = [x for x in L[1:] if x<p]
        L2 = [x for x in L[1:] if x>=p]
        LT1=quicksort(L1)
        LT2=quicksort(L2)
        return LT1 + [p] +LT2

#Courbe du tri rapide d'une liste aléatoire
x3,y3=[],[]
for i in range(1,1000,10):
    testTimer=timeit.Timer(partial(quicksort,listeAlea(i,1000)))
    t3=testTimer.timeit(number=10)
    x3.append(i)
    y3.append(t3)

#On trace les 3 courbes
from pylab import legend
plt.plot(x1,y1,marker='*',c = "r")
plt.plot(x2,y2,marker='*',c='b')
plt.plot(x3,y3,marker='*', c = 'g')
plt.title('Etude Experimentale des trois tris')
legend(['Tri à bulle','Tri d une liste aléatoire','Tri rapide d une liste aléatoire'])
Out[7]:
<matplotlib.legend.Legend at 0x2150d5539b0>
In [ ]:
#Compléxité du Tri d'une liste aléatoire est de O(nlog(n))
#Compléxité du Tri rapide d'une liste aléatoire est de O(nlog(n))
#Compléxité du Tri à bulle d'une liste est de O(n²)

3. Décider si une liste est triée

  1. Pour utiliser la recherche dichotomique, il est nécessaire d'avoir une liste triée. Écrivez la fonction estTrie qui renvoieTrue si la liste fournie en entrée est triée et False sinon.
In [8]:
#Question 3.1

#Methode 1

def estTrie(L):
    for i in range(len(L)-1): #On parcourt toute la liste (L) -1 pour eviter que L[i+1] sorte de la liste
        if L[i]>L[i+1]:  #lorsque un élement est supérieur à l'élement suivant --> faux sinon vrai
            return False
    return True

L=[1,2,3,4]
estTrie(L)
Out[8]:
True
In [9]:
#Methode 2 plus simple

def estTrie2(L):
    if L == sorted(L):
        return True
    return False

L=[6,3,4,2,5,1]
estTrie2(L)
Out[9]:
False
  1. Améliorez la fonction de recherche dichotomique pour qu'elle teste au préalable si la liste fournie en entrée est triée ou non. Si elle ne l'est pas, triez-la par la fonction de tri la plus efficace.
In [43]:
#Question 3.2

def recherche_dichotomique(x,L):
    a = 0
    b = len(L)-1
    m = (a+b)//2
    while a < b :
        if L[m] == x:
            return m
        elif L[m] > x :
            b = m-1
        else :
            a = m+1
        m = (a+b)//2
    return a


def amelio(x,L):
    if estTrie(L) == False:
        return recherche_dichotomique(x,sorted(L))
    else:
        return recherche_dichotomique(x,L)
    

L=[1,5,3,4] 
amelio(4,L)

#Dans ce cas de figure la fonction Amelio va donner la position de l'élement x dans la liste L triée préalablement.
Out[43]:
2
  1. Pensez-vous qu'il est intéressant (du point de vue de la complexité en temps) de tester si la liste est triée avant de faire une recherche dichotomique? (vérifiez les complexité avec et sans décider si la liste est triée).
In [57]:
#Question 3.3

#la recherche dichotomique réduit le tableau en 2 parties et facilite le parcour
#Mais si la liste n'est pas triée au préalable,il se peut que l'élément recherché se trouve dans les deux tableaux  
#ou plus loin qu'il ne devrait etre dans une liste triée.
#Conclusion, si la liste est triée , la recherche dichotomique est bien plus efficace et rapide que si la liste n'est pas triée.


#Etude expérimentale de la recherche dichotomique sur une liste triée et non triée:

def recherche_dichotomique(x,L):
    a = 0
    b = len(L)-1
    m = (a+b)//2
    while a < b :
        if L[m] == x:
            return m
        elif L[m] > x :
            b = m-1
        else :
            a = m+1
        m = (a+b)//2
    return a

def listeAlea(n,max):
    return [randint(1,max) for i in range(n)]


xavec,yavec=[],[]
L2 = []
for i in range(1,100,10):
    L2.append(i)
    testTimer=timeit.Timer(partial(recherche_dichotomique,i,L2))
    tavec=testTimer.timeit(number=10)
    xavec.append(i)
    yavec.append(tavec)
    
xsans,ysans=[],[]
for i in range(1,100,10):
    testTimer=timeit.Timer(partial(recherche_dichotomique,i,listeAlea(i,1000)))
    tsans=testTimer.timeit(number=10)
    xsans.append(i)
    ysans.append(tsans)
                           
plt.plot(xavec,yavec,marker='*',c = "r")
plt.plot(xsans,ysans,marker='*',c='b')
Out[57]:
[<matplotlib.lines.Line2D at 0x2150d687400>]
In [ ]:
#On observe graphiquement que la recherhce dichotomique est plus coûteuse dans une liste non triée que dans une liste triée.

4. Complexité de la recherche dichotomique

  1. Vérifiez expérimentalement que la complexité de la recherche dichotomique (dans une liste triée) est logarithmique. On rappelle que cette complexité est maximale lorsqu'on cherche un élément qui n'est pas dans la liste.
In [77]:
#Etude expérimentale de la recherche dichotomique sur une liste triée :

def recherche_dichotomique(x,L):
    a = 0
    b = len(L)-1
    m = (a+b)//2
    while a < b :
        if L[m] == x:
            return m
        elif L[m] > x :
            b = m-1
        else :
            a = m+1
        m = (a+b)//2
    return a


xavec,yavec=[],[]
L2 = []
for i in range(1,1000,10):
    L2.append(i)
    testTimer=timeit.Timer(partial(recherche_dichotomique,i,L2))
    tavec=testTimer.timeit(number=10)
    xavec.append(i)
    yavec.append(tavec)
    
                           
plt.plot(xavec,yavec,c = "r")
Out[77]:
[<matplotlib.lines.Line2D at 0x2150eeb2dd8>]
In [ ]:
#D'apres les resultats obtenus , on peut observer graphiquement que la courbe à bien une tendance logarithmique.