tri-analyse.py

# Comparaison des différents tris
import time
import random
import matplotlib.pyplot as plt
import numpy as np

# On commence par définir une petite méthode "utilitaire" qui va nous servir souvent.
# permute permet de permuter deux éléments situés aux indices i et j d'un tableau.
def permute(tab, i, j):
    '''
    :e/s: tab, un tableau d'éléments
    :entrees i et j: (int) les indices des éléments à permuter
    :pre-cond: i et j sont des indices valides dans tab
    :post-cond: le tableau est modifié, deux valeurs sont perumtées
    '''
    temp = tab[i]
    tab[i] = tab[j]
    tab[j] = temp

# Tri par sélection
# Rappel : on recherche le minimum du tableau, et on le permute avec l'élément dans la première case.
#          Ensuite, on recherche le minimum dans le reste du tableau, et on le permute avec l'élément dans la 2ème case.
#          Et ainsi de suite...


def triSelection(tab):
    '''
    :e/s tab: tableau (de float)
    :post-cond:
       - ∀ i ∈ [0;len(tab)[, ∃ j ∈ [0;len(tab)[,  tabₛ[j] = tabₑ[i]
         (les éléments de tab ont simplent changé d'ordre)
       - ∀ i ∈ [1;len(tab)[,  tabₛ[i] ≥ tabₛ[i-1]
         (les éléments de tab sont triés par valeur croissante)
    :complexité : 𝓞(n²)
    '''
    for i in range(len(tab)-1):
        indice_min = i
        
        # Boucle de recherche du minimum dans le tableau restant
        for j in range(i+1,len(tab)):
            if tab[j]<tab[indice_min]: 
                indice_min=j
        
        # Une fois le min trouvé, on le permute pour le mettre à sa place
        permute(tab, i, indice_min)
        

# Tri par insertion 
# Rappel : on considère que le "début" du tableau est trié. 
#          On se place au niveau de la première valeur non triée, et on la décale à gauche jusqu'à ce qu'elle trouve sa place
#          Observez que la partie gauche du tableau est déjà triée... 


# On commence par écrire une petite fonction utilitaire (une autre).
# Cette fonction prend un élément à un indice i, et le décale sur 
#   sa gauche jusqu'à ce qu'il soit à sa place... en faisant 
#   l'hypothèse que tous les éléments sur sa gauche sont bien triés.

def insereElt(tab, i):
    '''
    :e/s tab: tableau d'éléments
    :entrée i: int
    :pré-cond:
       - 1 ≤ i < len(tab)
       - ∀ j ∈ [1;i[,  tab[j] ≥ tab[j-1]  (tab est trié entre 0 et i-1)
    :post-cond:
       - ∀ j ∈ [0;i+1[, ∃ k ∈ [0;i+1[,  tabₛ[k] = tabₑ[j]
         (les éléments entre 0 et i+1 ont simplement changé d'ordre)
       - ∀ j ∈ [i+1;len(tab)[,  tabₛ[j] = tabₑ[j]
         (les éléments au delà de i n'ont pas été modifiés)
       - ∀ j ∈ [1;i+1[,  tab[j] ≥ tab[j-1]
         (tab est trié entre 0 et i)
    '''
    while (tab[i-1] > tab[i]) and i>0 :
        permute(tab, i, i-1)
        i -= 1   

# On écrit ensuite l'algo principal qui consiste à prendre
#  tour à tour chaque élément "non trié", et à l'insérer dans
#  le tableau trié (c'est-à-dire à le décaler jusqu'à sa bonne
#  place sur sa gauche). 
def triInsertion(tab):
    '''
    :e/s tab: tableau d'éléments
    :pré- et post-conditions usuelles
    '''
    for i in range(1,len(tab)):
        insereElt(tab, i)


# Tri binaire, ou quicksort
# Le quicksort est un tri récursif par excellence. 
# Le principe est que l'on choisit une valeur pivot, 
#   on range toutes les valeurs plus petites que le pivot à gauche du pivot
#   et toutes les valeurs plus grandes à droite. 
# Ensuite, on applique la même démarche sur les sous-tableaux gauche et droite. 
# Une simulation intéressante est disponible ici : 
# http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html


# On définit une méthode utilitaire qui va nous aider à partitionner notre tableau autour d'un pivot
def partitionne(tab, imin, imax):
    '''
    :e/s tab: tableau d'éléments 
    :entrée imin: int
    :entrée imax: int
    :sortie idroite: int
    :pré-cond: 0 ≤ imin ≤ imax < len(tab)
    :post-cond:
       - imin ≤ idroite ≤ imax
       - ∀ i ∈ [0;imin[ U ]imax;len(tab)[, tabₛ[i] = tabₑ[i]
         (tab n'est pas modifié en dehors de la plage [imin;imax])
       - ∀ i ∈ [imin;imax], ∃ j ∈ [imin;imax],  tabₛ[j] = tabₑ[i]
         (les éléments de tab ont simplent changé d'ordre entre imin et imax)
       - ∀ i ∈ [imin;idroite], tabₛ[i] ≤ tabₛ[idroite]
         (les éléments à gauche du pivot lui sont inférieurs ou égaux)
       - ∀ i ∈ ]idroite;imax], tabₛ[i] > tabₛ[idroite]
         (les éléments à droite du pivot lui sont supérieurs)
    '''
    pivot = tab[imin] # On choisit arbitrairement le premier élément comme pivot 

    igauche = imin + 1
    idroite = imax
    fini = False
    while not fini:
        while igauche <= idroite and tab[igauche] <= pivot:
            igauche = igauche + 1
        while tab[idroite] >= pivot and idroite >= igauche:
            idroite = idroite - 1
        if idroite < igauche:
            fini= True
        else:
            temp = tab[igauche]
            tab[igauche] = tab[idroite]
            tab[idroite] = temp
            #permute(tab, igauche, idroite)
    temp = tab[imin]
    tab[imin] = tab[idroite]
    tab[idroite] = temp
    #permute(tab, imin, imax)
    return idroite


# Si notre tableau n'est pas vide, on appelle tri_rec :
# Sinon, le tableau vide n'est pas modifié. 
def triRecursif(tab):
    if len(tab) > 0:
        tri_rec(tab, 0, len(tab)-1)

def tri_rec(tab, imin, imax):
    '''
    :e/s tab: tableau d'éléments
    :entrée imin: int
    :entrée imax: int
    :pré-cond: 0 ≤ imin ≤ imax < len(tab) (les indices existent dans le tableau)
    :post-cond:
       - ∀ i ∈ [0;imin[ U ]imax;len(tab)[, tabₛ[i] = tabₑ[i]
         (tab n'est pas modifié en dehors de la plage [imin;imax])
       - ∀ i ∈ [imin;imax], ∃ j ∈ [imin;imax],  tabₛ[j] = tabₑ[i]
         (les éléments de tab ont simplent changé d'ordre entre imin et imax)
       - ∀ i ∈ [imin;imax[,  tabₛ[i+1] ≥ tabₛ[i]
         (tab est trié entre imin et imax)
    '''
    if imin < imax:
        # partition the list
        pivot = partitionne(tab, imin, imax)
        # sort both halves
        tri_rec(tab, imin, pivot-1)
        tri_rec(tab, pivot+1, imax)
    return tab

# Tri bulle 
def triBulle(tab):
    '''
    :entree/sortie: tab un tableau d'éléments
    :post-condition : tab est trié
    ''' 
    swap = True
    while swap == True:
        swap = False
        for j in range(0,len(tab)-1):
            if tab[j]>tab[j+1]:
                swap = True
                temp=tab[j]
                tab[j]=tab[j+1]
                tab[j+1]=temp




nvalues = [10, 100, 500, 1000]
timesSelection = []
timesInsertion = []
timesBulle = []
timesRecursif = []

for i in nvalues:
    random.seed()
    p = 12**2 # Ordre de grandeur des valeurs
    liste = []
    
    for x in range(i): liste.append(random.randint(0, p))

    tableau = list(liste)
    a=time.process_time()
    triSelection(tableau)
    if x <= 10:
        print(tableau)
    b=time.process_time()
    timesSelection.append(b-a)

    tableau = list(liste)
    a=time.process_time()
    triInsertion(tableau)
    if x <= 10:
        print(tableau)
    b=time.process_time()
    timesInsertion.append(b-a)

    tableau = list(liste)
    a=time.process_time()
    triRecursif(tableau)
    if x <= 10:
        print(tableau)
    b=time.process_time()
    timesRecursif.append(b-a)
    
    tableau = list(liste)
    a=time.process_time()
    triBulle(tableau)
    if x <= 10:
        print(tableau)
    b=time.process_time()
    timesBulle.append(b-a)

print(nvalues)

print(timesSelection)
print(timesInsertion)
print(timesRecursif)
print(timesBulle)


#xs = range(0,1000)
plt.plot(nvalues,timesSelection, "r-", label="Tri par sélection")
plt.plot(nvalues,timesInsertion, "g-", label="Tri par insertion")
plt.plot(nvalues,timesRecursif, "b-", label="Tri par récursif")
plt.plot(nvalues,timesBulle, "g--", label="Tri bulles")

#plt.plot(nvalues,timesRecursif, "b-", label="Quick sort")
#plt.plot(xs, sqrt(xs), "r-", label=" √n")
plt.title("Comparaison des performances des différents algorithmes de tri")



plt.savefig('analyse-tri.png')

# Outil pour tester les algos de tri à la main 
tableauATrier = [42,1,6,0,8,9,2,4,7,3,19,34,23,67,45,23,105,18,190,20]
triBulle(tableauATrier)
print(tableauATrier)