Algorithmes de tri

Algorithmes de Tri

Partie 1: Recherche d'un minimum et d'un maximum

On considère la fonction maximum qui renvoie la plus grande valeur d'un tableau T passé en argument de la fonction:

def maximum (T):

    M = T[0]

    for k in range(1, len(T)):

        if T[k] > M:

            indice = k

            M = T[k]

    return M

1.1  Ecrire un code qui teste cette fonction pour la liste  L = [ 5,8,7,9,6,4,5,12,15,1]

1.2  Ecrire la fonction minimum(T) qui renvoie l'indice ( la position dans T)  de la plus petite valeur d'un tableau T passé en argument de la fonction ( inspirez vous de la fonction maximum). Le tableau T contient une liste de nombres entiers naturels. Tester le code sur L = [ 5,8,7,9,6,4,5,12,15,1]

1.3  Ecrire la fonction occurences(T, e) qui renvoie le nombre d’occurrences d'un élément e  dans le tableau T (nombre de fois que e apparaît dans T). Tester le code sur L = [ 5,8,7,9,6,4,5,12,15,1]

1.4 Comment peut-on montrer que toutes ces fonctions ont un coût linéaire ?   Coût linéaire <=> complexité en temps O(n) : Si on double le nombre n de données à traiter, on peut estimer que l'on double le temps d'exécution de l'algorithme.

Partie 2: algorithmes de Tri

On cherche à trier une liste de cartes, on vous propose deux algorithmes ( par sélection et par insertion)

Tri  par sélection

Cartes = [V,R,9,7,10,As,8,D]

A l’issu du tri,  l’ordre devra être Cartes = [7,8,9,10,V,D,R, As]

Ci-dessous,  l’élément coloré est l’élément en cours de traitement (la carte analysée), les éléments placés avant l’élément coloré sont déjà triés. La colonne indice contient l’indice de la carte dans la liste. Le tri par sélection consiste à permuter l’élément en cours de traitement (la Carte analysée) avec le plus petit élément de la zone non encore triée (la carte à échanger). On commence par le premier élément de liste, le valet V :

2.1  Complétez  le tableau ci-dessous :

2.2  On donne le pseudo-code de la fonction tri sélection

tri_selection ( tableau_à_trier)

   pour i allant de 0 à longueur(tableau_à_trier)-2

       indice_minimum <- i    # variable indice_minimum est initialisée à la valeur de i

       pour j allant de i+1 à longueur(tableau_à_trier)-1

           si tableau_à_trier[j] < tableau_à_trier[indice_minimum] alors

               indice_minimum <- j

           fin si

           si indice_minimum est différent de i

               échanger tableau_à_trier[i] et tableau_à_trier[indice_minimum]

           fin si

       fin pour j

    fin pour i

 Coder la fonction tri_selection  en python et tester pour la liste  L = [ 5,8,7,9,6,4,5,12,15,1]

   

2.3  Comment peut-on montrer que cette fonction à un coût quadratique ?   Coût quadratique <=> complexité en temps O(n2) : Si on double le nombre n de données à trier, on peut estimer que l'on multiplie par 4 le temps d'exécution de l'algorithme.

2.4  Un invariant de boucle est une propriété qui reste vraie avant, pendant et après l'exécution du code d'un algorithme, cette propriété prouve la correction partielle d'un algorithme  (  l'invariant prouve que l'algorithme est correct), parmi les propositions ci-dessous, laquelle peut être choisie comme invariant de boucle:

1. à la fin de l'étape i, tous les éléments d'indice de 0 à i sont triés.
2. Au début de l'étape i, si un élément e est à droite de la partie entre 0 et L[i], il est forcément plus grand que L[i]
3. à la fin de l'étape i, tous les éléments d'indice de 0 à n sont triés. On appelle n le nombre d'éléments de la liste.

Tri  par insertion

Cartes = [V,R,9,7,10,As,8,D]

A l’issu du tri,  l’ordre devra être Cartes = [7,8,9,10,V,D,R, As]

Ci-dessous,  l’élément coloré est l’élément en cours de traitement (la carte analysée). Le tri par insertion consiste à insérer la carte analysée à la bonne place en la comparant aux éléments qui la précède. la carte analysée étant en position i dans la liste,  on mémorise la valeur de la carte, on décale (si nécessaire) les cartes mal placées jusqu'en i.  On insère la carte analysée à l'emplacement voulu.

2.5 Complétez  le tableau ci-dessous :

 

2.6  On donne le pseudo-code de la fonction tri insertion

tri_insertion ( tableau_à_trier)

   pour i allant de 0 à longueur(tableau_à_trier)-1

       j <- i    # variable j est initialisée à la valeur de i

       x <- tableau_à_trier[i]

       tant que j > 0  et tableau_à_trier[j-1] > x

           tableau_à_trier[j] = tableau_à_trier[j-1]

           j <- j-1

       fin tant que

       tableau_à_trier[j] <- x      

    fin pour i

 Coder la fonction tri_insertion en python et tester pour la liste  L = [ 5,8,7,9,6,4,5,12,15,1]

2.7  Comment peut-on être sûr que la boucle "tant que" va se terminer?

2.8 La dernière colonne du tableau ci-dessus décrit les comparaisons nécessaires pour évaluer les éléments à déplacer. Quelle partie de l'algorithme réalise cette comparaison?

Partie 3:  mesure du temps d'exécution d'un algorithme de tri

Pour mesurer le temps d'exécution d'un algorithme de tri, on peut utiliser les fonctions du module time et plus particulièrement sa fonction perf_counter() qui renvoie un temps en seconde basé sur l'heure système. Par soustraction de deux mesures de perf_counter(), l'une avant de lancer le tri et l'autre à la fin de son exécution on aura le temps écoulé pour trier.

from time import perf_counter

départ = perf_counter() # mesure du temps au lancement du tri

tri_insertion(tableau_à_trier) # appel de la fonction de tri

fin = perf_counter() # mesure du temps à la fin du tri

temps_de_tri = round(fin - départ,1)

Les variables départ, fin et temps_de_tri contiendront un nombre flottant. La fonction round(nombre_flottant, 1)  avec ici le deuxième argument à 1 arrondit  la valeur de la variable nombre_flottant  à la décimale supérieure  ( 3.65 devient 3.7)

Pour générer une liste de n données , on peut écrire une fonction qui génère aléatoirement  n nombres dans la plage [ minimum , maximum ] :

from random import *

# fonction qui génère une liste L de n nombres aléatoires compris entre minimum et maximum

def tableau_aleatoire(nombre_de_données, minimum, maximum):

    L = []

    for i in range(nombre_de_données):

        L.append(randint(minimum,maximum))

    return L

Le code de la mesure pourra être comme ci-dessous:

from random import *

from time import perf_counter

def tableau_aleatoire(nombre_de_données, minimum, maximum):

    L = []

    for i in range(nombre_de_données):

        L.append(randint(minimum,maximum))

    return L

def tri_insertion(tableau_à_trier):

    # à compléter avec le code de la question 2.6

# le programme principal:

n=500

tableau = tableau_aleatoire(n,0,100)

départ = perf_counter()

tri_insertion(tableau)

fin = perf_counter()

print ("temps_de_tri =", round(fin - départ,1))  

3.1  Mesurer le temps de tri par insertion pour n=1000 données

3.2  Modifier le code du programme principal pour mesurer et afficher le temps de tri pour n variant de 0 à 16000 données avec un pas de 4000 données ( mesure pour n=0, n=4000, n=8000, n=12000, n=16000)

Il peut être intéressant de tracer la courbe du temps de tri en fonction du nombre de données, le module matplotlib permet de tracer des courbes avec python:

import matplotlib.pyplot as plt

from random import *

from time import perf_counter

# on crée deux listes pour récolter les données

taille = []

temps = []

for n in range(0, 20000, 2000):  

    print( "nombre de données:", n)

    taille.append(n) # ajout de n dans la liste taille

    tableau = tableau_aleatoire(n,0,100) # remplissage du tableau de n données aléatoires

    départ = perf_counter() # mesure du temps au lancement du tri

    tri_insertion(tableau) # appel de la fonction de tri

    fin = perf_counter() # mesure du temps à la fin du tri

    temps.append(round(fin - départ,1))  # calcul puis ajout du temps de tri dans la liste temps

    print(" =>  temps_de_tri:", round(fin - départ,1), "s" ) # affichage du temps à l’écran

# tracé de courbe

plt.title('temps en fonction de n valeurs')

plt.xlabel('n valeurs')

plt.ylabel('temps (en secondes)')

plt.grid(True)

plt.xlim(0,18000) # plage des abscisses entre 0 et 18000 données

plt.ylim(0,30)# plage des ordonnées entre 0 et 30s

plt.plot(taille,temps,':ob', lw=1) # :ob afficher un point rond et lw=1 largeur tracé = 1px

plt.show()

3.3  Tracer la courbe du temps de tri pour n variant de 0 à 16000 données avec un pas de 4000 données

3.4 Utiliser votre fonction maximum(T) de la partie 1 pour récupérer la valeur max du temps de tri que l'on pourra utiliser dans  plt.ylim(...) afin d'avoir une courbe qui remplit mieux la zone d'affichage.

3.5  Le résultat de l'affichage montre-t-il comme pour le tri par sélection  un coût quadratique ?  

Créé avec HelpNDoc Personal Edition: Avantages d'un outil de création d'aide