NSI : listes et algorithmes de tris

Exercices

Exercice 1

Ecrire une fonction permettant de renvoyer la liste des n nombres entiers classés par ordre croissant entre 1 et n

>>> liste_ordonnee(5)
[1, 2, 3, 4, 5]

Exercice 2

Ecrire une fonction permettant de renvoyer une liste de n nombres entiers aléatoires compris entre 1 et 1000.

>>> liste_aleatoire(5)
[178, 502, 274, 440, 480]

Exercice 3

Ecrire une fonction triee() permettant de déterminer si une liste est triée par ordre croissant

>>> a=[7,3,6]
>>> triee(a)
False
>>> b=[5,8,15]
>>> triee(b)
True

Proposition correction exercices 1 et 2

# proposition 1
def liste_ordonnee(n):
    # on crée une liste vide
    liste=[]
    # i parcourt les valeurs de 1 à n
    for i in range(1,n+1):
        # on ajoute i à la liste
        liste.append(i)
    # on retourne la liste
    return liste

# proposition 2

def liste_ordonnee_bis(n):
    return [i for i in range(1,n+1)]

from random import randint

def liste_aleatoire(n):
    return [randint(1,1000) for i in range(n)]

2. Méthodes de tris

Pour pouvoir étudier des données, il est souvent nécessaire de les trier par ordre croissant ou décroissant.
Il existe différentes méthodes pour cela.
Ces algorithmes diffèrent par leurs complexités et leurs efficacités.
Pour visualiser différents algorithmes de tri :
https://www.toptal.com/developers/sorting-algorithms

A. permuter le contenu de deux variables

Il est souvent nécessaire en informatique et plus particulièrement sur les algorithmes de tris de permuter le contenu de deux variables.
Pour cela, on a souvent besoin d’utiliser une troisième variable temporaire

>>> a=5
>>> b=8
>>> a=b
>>> a
8
>>> b
8
>>> a=5
>>> b=8
>>> temp=a
>>> a=b
>>> b=temp
>>> a
8
>>> b
5
# en python, il n'est pas nécessaire d'utiliser cette variable intermédiaire, on peut avoir recours à une affectation par tuple
>>> a=5
>>> b=8
>>> a,b=b,a
>>> a
8
>>> b
5
>>> a=[1,3,7,4]
>>> a[0],a[3]=a[3],a[0]
>>> a
[4,3,7,1]

B. Tri par sélection

Exercice 5

Après avoir lu la partie de l’article sur les algorithmes de tris de la revue Interstice sur le tri par sélection, écrire une fonction tri_selection() permettant de ranger par ordre croissant une liste passée en paramètre en utilisant cette méthode.

>>> # par exemple
>>> a=[7,2,1,6]
>>> tri_selection(a)
>>> [1,2,6,7]

Exercice 6

Ecrire une fonction ordre_decroissant_liste(a) permettant de ranger par ordre décroissant une liste passée en paramètre.
Cette fonction pourra utiliser les deux fonctions précédentes.

>>> # par exemple
>>> a=[7,2,1,6]
>>> ordre_decroissant_liste(a)
>>> [7,6,2,1]

C. Tri par propagation ou tri bulle.

Exercice 7

Après avoir lu la partie de l’article sur les algorithmes de tris de la revue Interstice sur le tri bulle, écrire une fonction tri_bulle() permettant de ranger par ordre croissant une liste passée en paramètre en utilisant cette méthode.

>>> # par exemple
>>> a=[7,2,1,6]
>>> tri_bulle(a)
>>> [1,2,6,7]

Proposition correction algorithmes de tris

Un premier fichier présentant les 3 algorithmes de tris vus en cours :

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))

Un second programme permettant de comparer le temps mis par ces différents algorithmes :

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.savefig("graphique "+type_tri+".png")
    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("graphique comparaisons.png")
    pylab.show()



comparaison_tris(1000)