Tris

Problématique

On a vu dans la recherche dichotomique de l'intérêt d'avoir un tableau ordonné pour pouvoir rechercher plus rapidement un élément à l'intérieur

Comment ordonne-t-on un tableau?

Nous allons voir deux algorithmes de tri, le tri par sélection et le tri par fusion

Nous allons aussi comparer leur complexité

Tri par sélection (par ordre croissant)

La première idée est de parcourir le tableau du début à la fin afin de sélectionner le plus petit élément puis d'échanger les places du premier élément du tableau avec celle du plus petit élément

Ensuite on parcourt le tableau de la deuxième place jusqu'à la fin pour sélectionner le plus petit élément puis d'échanger les places du deuxième élément du tableau avec celle du plus petit élément

Voici sur un exemple le tri par sélection

Une première fonction selection(i,liste) retourne l'indice pos du plus petit élément de la liste à partir de l'élément en position i


def selection(i,liste):
    '''retourne l'indice pos du plus petit élément de la liste
    liste entre i (inclus) jusqu'à la fin de la liste'''
    
    
    pos = 0
    min = liste[i]
    for k in range(i+1,len(liste)):
        if liste[k] < min:
            min = liste[k]
            pos = k
    return pos

Puis une deuxième fonction echange(i,j,liste) qui échange de place liste[i] et liste[j]


def echange(i,j,liste):
    '''échange les éléments liste[i] et liste[j]'''
    temp = liste[i]
    liste[i] = liste[j]
    liste[j] = temp

Exercices

  1. Tester avec doctest la fonction selection(i,liste)
  2. Ecrire la fonction triSelection(liste)
  3. Prouver la
  4. Evaluer la complexité du tri par séléction en comptant le nombre de comparaisons effectuées sur une liste de longueur n
  5. Faire trois tests chronométrés sur les listes.Qu'observez vous ?
    • LISTE1 = [i for i in range(100000)]
    • LISTE2 = [i for i in range(99999,-1,-1)]
    • faire import random puis random.shuffle(LISTE1) puis chronométrer triSelection sur LISTE1
  6. Donner une estimation dans le meilleur des cas du temps d'exécution de triSelection sur une liste de 10000 nombres

  7. Donner une estimation dans le pire des cas du temps d'exécution de triSelection sur une liste de 10000 nombres

  8. Donner une estimation du temps moyen d'exécution de triSelection sur une liste de 10000 nombres

  9. Donner une estimation du temps moyen d'exécution de triSelection sur une liste de 100000 nombres par calcul

Tri par fusion

la deuxième idée est de réutiliser la dichotomie pour améliorer la performance du tri

Trier un tableau revient à le couper en deux parties à peu près égales, trier chaque sous-partie et fusionner les deux parties triées en une seule

La difficulté n'est pas de trier les sous-parties car en procédant récursivement on va descendre jusqu'à la cellule qui est triée!, non la difficulté est comment fusionner en un autre tableau deux tableaux triés?

Voici comment on va procéder

Supposons que l'on a fusionné une partie des deux listes, on compare les deux éléments liste1[i] et liste2[j], le plus petit des deux ira dans la liste3 et on met à jour les variables i,j et k

Voici la fonction fusion(liste1,liste2)


def fusion(liste1,liste2):
    '''retourne une liste triée dans l'ordre croissant résultat de la
    fusion des deux listes liste1 et liste2'''
    liste3 = []
    i = 0
    j = 0
    
    while i < len(liste1) and j < len(liste2):
        if liste1[i] < liste2[j]:
            liste3.append(liste1[i])
            i = i + 1
            
        else:
            liste3.append(liste2[j])
            j = j + 1
            
    if i == len(liste1):
        for x in liste2[j:]:
            liste3.append(x)
    if j == len(liste2):
        for x in liste1[i:]:
            liste3.append(x)
    return liste3

Exercices

  1. Tester avec doctest la fonction fusion(liste1,liste2)
  2. Ecrire la fonction récursive triFusion(liste)
  3. Prouver la
  4. Evaluer la complexité du tri par fusion
  5. Faire trois tests chronométrés sur les listes.Qu'observez vous ?
    • LISTE1 = [i for i in range(100000)]
    • LISTE2 = [i for i in range(99999,-1,-1)]
    • faire import random puis random.shuffle(LISTE1) puis chronométrer triFusion sur LISTE1
  6. Donner une estimation dans le meilleur des cas du temps d'exécution de triFusion sur une liste de 10000 nombres

  7. Donner une estimation dans le pire des cas du temps d'exécution de triFusion sur une liste de 10000 nombres

  8. Donner une estimation du temps moyen d'exécution de triFusion sur une liste de 10000 nombres

  9. Donner une estimation du temps moyen d'exécution de triFusion sur une liste de 100000 nombres par calcul