duranton.net

Chapitre 9 : Diviser pour régner.

Rappel :

Vous avez vu l'année dernière le tri par insertion et le tri par selection et tous les deux avaient une complexité en \(\mathcal{O}\left(n^2\right)\).

1. Diviser pour régner:

A copier dans le cahier.

L'expression "diviser pour régner" en informatique est utilisée pour décrire un algorithme fractionnant un problème, ou des données en éléments plus petits afin de les traiter.

Page wikipedia en français.

Page wikipedia en anglais.

2. Exercice : (sujet 9 - 2025)

On s’intéresse à la recherche dichotomique dans un tableau trié d’entiers.

Compléter la fonction suivante en respectant la spécification.

Exemples :

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
False
def dichotomie(tab, x): """ tab : tableau d'entiers trié dans l'ordre croissant x : nombre entier La fonction renvoie True si tab contient x et False sinon """ debut = 0 fin = len(tab) - 1 while debut <= fin: m = ... if x == tab[m]: return ... if x > tab[m]: debut = m + 1 else: fin = ... return ...

Tests :

Affichage :

Console:


    

      >>>
      
    

  












    
3. Le tri par fusion

    
A copier dans le cahier.

    
Le tri par fusion est un algorithme de tri d'une liste qui fonctionne par récurrence à l'aide du principe de diviser pour régner.

    
 Page wikipedia 

    
Sa complexité est en \(\mathcal{O}\left(n \log(n)\right)\).








  
4. Exercice : fusion!


  

    
Compléter la fonction fusion(liste1,liste2), qui prend comme paramètres deux listes triées et qui renvoie une liste triée composée des éléments des deux autres.

 
  


  
  
def fusion(liste1,liste2):
    '''
    fusion prend deux listes triées et retourne une grande liste triée contenant les éléments des deux autres.
    '''
    final = []   # liste qui sera retournée
    curseur1 = 0 # curseur de la liste1
    curseur2 = 0 # curseur de la liste2
    while ......................................................  : # tant qu'il reste des éléments non traités dans une des deux listes
        if ............... : # le plus petit élément est dans la liste 1
            final.append(liste1[curseur1])
            curseur1 += 1
        else: # le plus petit élément est celui de la liste 2
            ......................
            ......................

    if ......................... : # il reste des éléments dans la liste 2 à traiter
        for i in range(curseur2, len(liste2)):
            final.append(.......)
    else : # il reste des éléments dans la liste 1 à traiter
        for i in range(curseur1, len(liste1)):
            final.append(.......)
    return final

# données de test
listeA = [2, 5, 7, 8, 9, 11, 13, 15, 19, 21, 25, 29, 35, 38, 39, 40, 52, 69, 78, 89]
listeB = [3, 4, 5, 7, 12, 14, 15, 18, 23, 30, 32, 33, 34, 42, 53]


  
  

  
Tests :

  


  
Affichage :

  


  
Console:

  

    

    

      >>>
      
    

  











  
5. Exercice : tri fusion


  

    
Compléter la fonction tri_par_fusion(liste) en vous appuyant sur la fonction fusion (fusion de deux listes triées) de l'exercice précédent.

  


  
  
def fusion(liste1, liste2):
    """Fusionne deux listes triées en une liste triée (avec doublons conservés)."""
    # RECOPIER LA FONCTION COMPLETEE DE L EXERCICE PRECEDENT





def tri_par_fusion(liste):
    """Retourne une nouvelle liste triée par la méthode "diviser pour régner" (merge sort)."""
    if ...:  # Il y a un élément dans la liste ou moins.
        return liste
    else:
        moitie = ...  # indice correspondant au milieu de la liste
        gauche = tri_par_fusion(...)   # partie gauche
        droite = tri_par_fusion(...)   # partie droite
        return fusion(gauche, droite)
    
    
liste = [142, 92, 86, 483, 87, 997, 515, 243, 193, 175, 680, 226, 794, 332,
 534, 305, 656, 393, 66, 659, 361, 362, 387, 469, 274, 343, 471, 443, 982, 786, 636,
  587, 768, 966, 816, 959, 438, 784, 584, 196, 515, 249, 737, 704, 635, 572, 101, 209,
   298, 832, 338, 750, 922, 566, 704, 113, 6, 560, 62, 451, 98, 708, 69, 600, 669, 404,
    685, 707, 440, 741, 423, 129, 545, 237, 178, 870, 654, 849, 453, 894, 60, 140, 777,
     894, 403, 672, 248, 627, 282, 723, 176, 994, 342, 806, 259, 422, 733, 644, 400, 3]
  
print(tri_par_fusion(liste))


  
  

  
Tests :

  


  
Affichage :

  


  
Console:

  

    

    

      >>>
      
    

  







    
6. Exercice : 

    
A faire dans le cahier.

    
Ce code a permis de générer les 3 images ci-dessous : 

    

        

            
        

        

            
        

        

            
        

    

    
Il peut sembler que les courbes soient similiaires mais :

    
    
        
  1. Comparer les performances de chaque tri.
    2. 
        
  2. A quelle courbe vue en seconde ressemble les deux premières ci-dessus?
    3. 
        
  3. Quel est l'aspect de la troisième courbe?
    4. 
        
  4. Dans les deux premières courbes:
            
      
                
    • Prendre deux points de la courbe dont les abscisses sont à peu près le double l'une de l'autre.
      • 
                
    • Calculer une approximation du rapport de ces ordonnées.
      • 
            
    
        
    5. 
        
  5. Dans les deux premières courbes:
            
      
                
    • Prendre deux points de la courbe dont les abscisses sont à peu près le triple l'une de l'autre.
      • 
                
    • Calculer une approximation du rapport de ces ordonnées.
      • 
            
    
        
    6. 
        
  6. Dans les deux premières courbes:
            
      
                
    • Prendre deux points de la courbe dont les abscisses sont à peu près le quadruple l'une de l'autre.
      • 
                
    • Calculer une approximation du rapport de ces ordonnées.
      • 
            
    
        
    7. 
        
  7. Dans la troisième courbe:
            
      
                
    • Prendre deux points de la courbe dont les abscisses sont à peu près le quadruple l'une de l'autre.
      • 
                
    • Calculer une approximation du rapport de ces ordonnées.
      • 
            
    
        
    8. 
    






    
7. A retenir !

    
A copier dans le cahier.

    
Les tris par insertion et par selection sont de complexités quadratiques en \(\mathcal{O}\left(n^2 \right)\).

    
Le tri par fusion est de complexité linéarithmique en \(\mathcal{O}\left(n \log(n)\right)\).