Aller au contenu

Exercices sur les tris

Rappel des fonctions du cours

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import random
import time
import matplotlib.pyplot as plt


%matplotlib notebook

def echange(t, i, j):
    """
    Permute les éléments situés aux index i et j du tableau t
    t: tableau non vide
    i, j: entiers dans l'intervalle [0, len(t)-1]
    """
    tmp = t[i]
    t[i] = t[j]
    t[j] = tmp

def selection(t):
    """
    trie par ordre croissant les éléments de t
    """
    n = len(t)
    #Compléter le code
    for i in range(n-1):
        idxmini = i
        for j in range(i+1, n):
            if t[j] < t[idxmini]:
                idxmini = j
        echange(t, i, idxmini)

def place(t, i):
    """ amène t[i] à sa place dans t[0..i-1] supposé trié"""
    elt_a_classer = t[i]
    j = i
    # décalage des éléments du tableau à droite, pour trouver la place de t[i]
    while j > 0 and t[j - 1] > elt_a_classer:
        t[j] = t[j - 1]
        j = j - 1
    # on insère l'élément à sa place
    t[j] = elt_a_classer

def insertion(t):
    """
    trie par ordre croissant les éléments de t
    """
    for i in range(1, len(t)):
        place(t, i)

La complexité des algorithmes de tri

Mesure du temps d'exécution d'un algorithme

Indications pour cette partie

La fonction help de python permet d'obtenir de l'aide sur une commande/fonction.
La fonction time.time() du module time donne l’heure en seconde. En l'appelant avant puis après une fonction, on a une estimation du temps d'exécution de celle-ci.
Une fonction peut être passée en paramètre d'une autre fonction. Par exemple si f est une fonction, l'appel ma_fonction(n, f) est valide en python.

  1. La fonction randint est présente dans le module random. Que réalise cette fonction ?
  2. Compléter la spécification de la fonction suivante 
    1
2
3
4
5
    def alea(n):
    """
    A compléter
    """
    return [random.randint(0, 100) for i in range(n)]
  3. Compléter la fonction tempstri(n, algo) qui prend en paramètre un entier naturel correspendant à la taille d’un tableau et une fonction de tri algo. Cette fonction renvoie le temps mis par l’algorithme de tri algo pour trier un tableau de taille . Tester votre fonction sur les deux tris vus en cours et dont les codes python sont disponible au début de ce sujet. 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    def tempstri(n, algo):
    """
    Renvoie le temps mis par un algorithme pour trier un tableau de taille n
    n: entier naturel
    algo: fonction de tri
    """
    t = alea(n)
    start = time.time()
    # A compléter

# TESTS - exemples
print(tempstri(1000, insertion))
print(tempstri(1000, selection))
0.05924797058105469  
0.037672996520996094

Interprétation de la complexité d'un algorithme

Indications pour cette partie

Pour les constructions de tableaux, penser aux constructions par compréhension.
Utiliser la fonction tempstri()

  1. On souhaite visualiser le temps d'exécution d'un algorithme en fonction de la taille du tableau. On construit d'abord un tableau taille qui contient les tailles des différents tableaux (de 1000 à 10000 par pas de 1000). On construit ensuite un tableau temps qui contient les temps mis par un algorithme algo pour trier un tableau dont la taille est un élément de taille. Donner le code qui permet de construire le tableau temps. 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    def trace(algo):
    """
    trace le graphe du temps d'exécution d'un algorithme en fonction de la taille du tableau
    algo: nom d'une fonction
    """
    taille = list(range(1000,11000,1000)) #Un tableau qui contient les tailles de tableau
    # Compléter la ligne suivante
    temps = [...]
    # Tracé - ne rien modifier ici
    fig = plt.figure()
    plt.title("Complexite tri par " + algo.__name__)
    plt.plot(taille,temps)#On trace la figure les tailles en abscisse,
    #les temps en ordonnées
    plt.xlabel('Taille tableau')
    plt.ylabel('Temps')
    plt.grid()
    plt.show()
  2. Tracer le graphique donnant le temps d'exécution si on utilise un tri par insertion puis par sélection.
  3. Justifier que la complexité de ces tri est quadratique. On pourra par exemple comparer les temps d'exécution pour trier un tableau de 2000 éléments puis de 6000 ou 10000 éléments.

Trié par ordre croissant ?

Ecrire une fonction est_trie(t) qui renvoie True si le tableau t est trié dans l’ordre croissant et False sinon.

Tri sans modification du tableau d'entrée

Les implémentations rencontrées jusqu'à présent effectuaient le tri en place, c'est-à-dire modifiaient le tableau à trier.
On demande ici d'écrire une fonction insert_non_mutable(t) qui réalise un tri par insertion du tableau t mais qui renvoie le résultat dans un nouveau tableau, laissant t inchangé. On modifiera légèrement la fonction place(t, i) pour résoudre ce problème.

Valeur plus fréquente ***

En utilisant un tri par insertion, écrire ne fonction plus_frequente(t) qui prend en paramètre un tableau d’entiers et qui renvoie la valeur la plus fréquente rencontrée dans le tableau. On peut remarquer que dans un tableau trié, des valeurs égales se retrouvent cote à cote.