Comparaison de tris

1. Comparaison temps d’exécution

Une manière empirique de déterminer quel est l’algorithme de tris le plus efficace entre le tri par insertion, le tri par bulles et le tri par sélection est de comparer leur temps d’exécution pour un certain nombre de tris de listes aléatoires de tailles données.

Dans votre fichier comportant vos différentes fonctions , on ajoute la fonction tri_sort()

from random import randint

def liste_aleatoire(n):
   

def inverse_liste(a):
   

def triee(a):
    

def tri_selection(a):
    

def tri_bulles(a):
    
def tri_insertion(a):
    

def tri_sort(a):
    b=a.copy()
    b.sort()
    return b

Copier et coller le script suivant dans un fichier situé dans le même répertoire que votre script de tris.

Modifier la 1ere ligne du script en remplaçant si besoin tris par le nom du module comportant vos algorithmes de tris.

import tris
from timeit import timeit
import pylab




#timeit(setup='from tris import tri_select; from listes import cree_liste_melangee',stmt='tri_select(cree_liste_melangee(10))',number=100)

def mesure_temps(tri,longueur):
    '''
    retourne le temps maximal pour trier par tri par sélection de 100 listes mélangées de longueur 10
    : longueur : (int) longueur des listes à trier
    : CU :
    : return : (list) une liste contenant le temps des listes de longueurs 1,2,......, longueur
    
    '''
    liste_temps=[]
    for i in range(0,longueur):
        temp = timeit(setup='from tris import '+ tri +'; from tris import liste_aleatoire',stmt=tri+'(liste_aleatoire('+str(i)+'))',number=100)
        liste_temps.append(temp)
    return liste_temps


def affichage(type_tri,longueur):
    '''
    affiche le graphique représentant les temps maximums pour 100 listes triées de taille donnée
    '''
    
    correspondance = {# on crée un dictionnaire de correspondances
    "selection":"tri_selection", # 
    "insertion":"tri_insertion",
    "bulles":"tri_bulles",
    "sort":"tri_sort",
    }
    

    longueur_listes=[i for i in range(1,longueur+1)]
    # return correspondance[type_tri]
    liste_temps=mesure_temps(correspondance[type_tri],longueur)
    NBRE_ESSAIS = 100
    pylab.title('Temps du tri '+type_tri+' (pour {:d} essais)'.format(NBRE_ESSAIS))
    pylab.xlabel('taille des listes')
    pylab.ylabel('temps en secondes')
    pylab.grid()
    pylab.plot(longueur_listes,liste_temps)
    pylab.show()

def comparaison_tris(longueur):
    longueur_listes=[i for i in range(1,longueur+1)]
    # return correspondance[type_tri]
    NBRE_ESSAIS = 100
    pylab.title('Temps cumulé pour trier {:d} listes aléatoires,'.format(NBRE_ESSAIS)+'\npour des listes de longueurs 1 à '+str(longueur)+'.')
    pylab.xlabel('taille des listes')
    pylab.ylabel('temps en secondes \npour {:d} listes '.format(NBRE_ESSAIS))
    pylab.grid()
    pylab.plot(longueur_listes,mesure_temps("tri_selection",longueur),label="tri_selection")
    pylab.plot(longueur_listes,mesure_temps("tri_insertion",longueur),label="tri_insertion")
    pylab.plot(longueur_listes,mesure_temps("tri_bulles",longueur),label="tri_bulles")
    pylab.plot(longueur_listes,mesure_temps("tri_sort",longueur),label="tri_sort")
    pylab.legend()
    pylab.savefig("graphique1.png")
    pylab.show()



affichage("selection",100)

On obtient alors :

affichage(« bulles »,100) donnera :

comparaison_tris(100)

A vous de tester vos scripts et de les optimiser éventuellement.

2. Proposition corrections algorithmes de tris

from random import randint

def liste_aleatoire(n):
    # générer aléatoirement un liste de taille n
    # contenant des nbres entiers entre 0 et 100
    return [randint(0,100) for i in range(n)]

def inverse_liste(a):
    # inverse les termes de la liste
    retour=[]
    for i in range(len(a)):
        retour.append(a[len(a)-1-i])
    return retour

def triee(a):
    # indique si une liste est triée
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True

def tri_selection(a):
    # trie une liste par ordre croissant
    # par l'algo de tri par selection
    liste=a.copy()
    for i in range(len(liste)-1):
        # pour voir le déroulement de l'algorithme
        # print(liste)
        indice_min=i
        for j in range(i,len(liste)):
            if liste[j]<liste[indice_min]:
                indice_min=j
        liste[i],liste[indice_min]=liste[indice_min],liste[i]
    return liste

def tri_bulles(a):
    # trie une liste par ordre croissant
    # par l'algo de tri par bulle
    liste=a.copy()
    for i in range(len(liste)):
        # pour voir le déroulement de l'algorithme
        #print(liste)
        for j in range(len(liste)-1):
            if liste[j+1]<liste[j]:
                liste[j+1],liste[j]=liste[j],liste[j+1]
                # pour voir le déroulement de l'algorithme
                #print(liste)
    return liste

def tri_insertion(a):
    # trie une liste par ordre croissant
    # par l'algo de tri par insertion
    liste=a.copy()
    for i in range(0,len(liste)-1):
        
        j=i+1
        val=liste[j]
        while j>0 and liste[j-1]>val:
            liste[j]=liste[j-1]
            j=j-1
            
        liste[j]=val
        #print(i,j,liste)
            
                
    return liste

def tri_sort(a):
    b=a.copy()
    b.sort()
    return b

# Pour tester les tris et comprendre leurs différents fonctionnements
#a=liste_aleatoire(10)
#print(a)
#print("Tri selection")
#tri_selection(a)
#print("tri bulles")
#tri_bulles(a)
#print("tri insertion")
#print(tri_insertion(a))
#print(tri_sort(a))