Algorithmes Première

Données triées

Tri par sélection

Code completÉtapes

def tri_selection(tab):   # (1)!
    for i in range(len(tab)):   # (2)!
        ind_min = i   # (3)!
        for j in range(i + 1, len(tab)):
            if tab[j] < tab[ind_min]:
                ind_min = j
        tab[i], tab[ind_min] = tab[ind_min], tab[i]   # (4)!

• Principe général : on place chaque valeur à sa place finale dans le tableau trié(5)
• La valeur à l'indice i dans le tableau trié est la i-ième plus petite valeur(6)
  • On calcule l'indice de la plus petite valeur sans toucher à la partie déjà triée(7)
  • On place la plus petite valeur à l'indice i(8)

Vidéo explicative

1. Principe général : on place chaque valeur à sa place finale dans le tableau trié
2. La valeur à l'indice i dans le tableau trié est la i-ième plus petite valeur
3. On calcule l'indice de la plus petite valeur sans toucher à la partie déjà triée
4. On place la plus petite valeur à l'indice i

5. def tri_selection(tab):
   

6.     for i in range(len(tab)):
   

7.         ind_min = i
           for j in range(i + 1, len(tab)):
               if tab[j] < tab[ind_min]:
                   ind_min = j
   

8.         tab[i], tab[ind_min] = tab[ind_min], tab[i]
   

Tri par insertion

Code completÉtapes

def tri_insertion(tab):   # (1)!
    for i in range(1, len(tab)):
        j = i   # (2)!
        while j > 0 and tab[j] < tab[j-1]:   # (3)!
            tab[j], tab[j-1] = tab[j-1], tab[j]
            j -= 1

• Principe générale : on insère les valeurs une par une dans la liste des valeurs précédemment triées(4)
• On définit un indice qui va suivre la valeur au fur et à mesure qu'on la décale vers le début de la liste(5)
• On décale la valeur d'un cran vers la gauche jusqu'à ce qu'elle soit bien placée (attention à ne pas oublier le cas où on arrive au tout début de la liste)(6)

Vidéo explicative

1. Principe générale : on insère les valeurs une par une dans la liste des valeurs précédemment triées
2. On définit un indice qui va suivre la valeur au fur et à mesure qu'on la décale vers le début de la liste
3. On décale la valeur d'un cran vers la gauche jusqu'à ce qu'elle soit bien placée (attention à ne pas oublier le cas où on arrive au tout début de la liste)

4. def tri_insertion(tab):
       for i in range(1, len(tab)):
   

5.         j = i
   

6.         while j > 0 and tab[j] < tab[j-1]:
               tab[j], tab[j-1] = tab[j-1], tab[j]
               j -= 1
   

Recherche dichotomique dans un tableau trié

Code completÉtapes

def recherche_dicho(tab, valeur):   # (1)!
    g = 0
    d = len(tab) - 1
    while g <= d:   # (2)!
        m = (g + d) // 2   # (3)!
        if tab[m] == valeur:   # (4)!
            return True
        elif tab[m] > valeur:   # (5)!
            d = m - 1
        else:   # (6)!
            g = m + 1
    return False   # (7)!

• Initialiser les indices de gauche et de droite délimitant l'intervalle de recherche(8)
• Tant que l'intervalle a au moins un élément :(9)
  • Calculer l'indice du milieu de l'intervalle(10)
  • Si la case du milieu contient la valeur recherchée, c'est gagné(11)
  • Si la case du milieu contient une valeur plus grande que la valeur recherchée, on doit regarder "dans la moitié gauche"(12)
  • Sinon la case du milieu contient une valeur plus petite que la valeur recherchée, on doit regarder "dans la moitié droite"(13)
• Si on sort de la boucle, la valeur n'est pas dans le tableau(14)

Vidéo explicative

Illustration ludique

1. Initialiser les indices de gauche et de droite délimitant l'intervalle de recherche
2. Tant que l'intervalle a au moins un élément :
3. Calculer l'indice du milieu de l'intervalle
4. Si la case du milieu contient la valeur recherchée, c'est gagné
5. Si la case du milieu contient une valeur plus grande que la valeur recherchée, on doit regarder "dans la moitié gauche"
6. Sinon la case du milieu contient une valeur plus petite que la valeur recherchée, on doit regarder "dans la moitié droite"
7. Si on sort de la boucle, la valeur n'est pas dans le tableau

8. def recherche_dicho(tab, valeur):
       g = 0
       d = len(tab) - 1
   

9.     while g <= d:
   

10.         m = (g + d) // 2
    

11.         if tab[m] == valeur:
                return True
    

12.         elif tab[m] > valeur:
                d = m - 1
    

13.         else:
                g = m + 1
    

14.     return False