Correction de la série d'exercices no 6

Exercice 6-1 : Tri par bulles

voir cours

Exercice 6-2 : Tri par fusion

La boucle récursive assure que lors de la fusion, on traite tous les éléments. Le principe consiste à séparer le tableau plusieurs fois en 2 et à trier des paires de 2 éléments. Les fonctions sont appelées de façon récursive tel que décrit ci-dessous.

(TF([T]) <=> Tri_par_fusion(): séparation de la liste [T];
Fusion([T],n1,n2): fusion d'une première liste (partie 1) qui contient n2 éléments avec une deuxième liste (partie 2). La longueur totale de la liste combinée [T] (qui contient partie 1 et partie 2) est n1>n2. 

TF (21 23 4 2 89 2 3 65 78 14 25 67 67 89 100 1 14 78 78)
       TF (21 23 4 2 89 2 3 65 78 14)
           TF (21 23 4 2 89)
		TF (21 23 4)
			TF (21 23)
 		           TF (21)
			   TF (23)
                           Fusion([21 23], 2, 1) -> [21 23]
   			TF(4)
			Fusion(21 23 4, 3, 2) -> [4 21 23]
		TF(2 89)
			TF(2)
			TF(89)
			Fusion([2 89], 2, 1) -> [2 89]
		Fusion([4 21 23 2 89], 5, 3) -> [2 4 21 23 89]
	TF(2 3 65 78 14)
		TF(2 3 65)
			TF(2 3)
	                   TF(2)
                       	   TF(3)
                           Fusion([2 3], 2, 1)->[2 3]
			TF(65)
			Fusion([2 3 65], 3, 2) -> [2 3 65]
		TF(78 14)
			TF(78)
			TF(14)
			Fusion([78 14],)
Etc...

Algorithme de fusion:
Il est important de comprendre comment marche la procédure Fusion. L'idée est de fusionner les deux parties déjà triées du tableau passé en paramètre et obtenir ainsi un tableau entièrement trié.

Fusion([T], 19, 10) avec T = [2 2 3 4 14 21 23 65 78 89 1 14 25 67 67 78 78 89 100]

On commence par créer un tableau temporaire U. On compare ensuite le premier élément des 2 parties triées et on place dans le tableau U le plus petit des deux éléments. On répète ainsi la procédure jusqu'à ce qu'un des deux tableaux soit vide. 

    
U[1] U[1 2] U[1 2 2] U[1 2 2 3] ... U[1 2 2 3 4 14 14 21 23 25 65 67 78 89]

Les éléments restants dans le deuxième tableau sont insérés à la suite dans le tableau temporaire jusqu'à le compléter entièrement. 

          
U[1 2 2 3 4 14 14 21 23 25 65 67 78 89 89 100]

On recopie le tableau temporaire U dans T

                        
T = U

Exercice 6-3 : Ordre de complexité - tri par fusion et tri par bulles

La profondeur est de log(16) = 4 et la largeur est de 16 (à chaque fois 16 opérations sont effectuées). La complexité est donc de nlog(n).

Pour 128 éléments:

Exercice 6-4 : Ordres de complexité

  1.  
    1. A: 10'000*5 = 50'000
      B: 2*52 = 50
      Le programme B est le plus rapide.
    2. Il faut résoudre l'équation 10 000 * x = 2 * x2. On obtient x = 5000.
    3. Pour N < 142, le programme C est plus rapide que le A
      Le programme C est toujours moins rapide que le B
  2. N = 2 E: 64 opérations F: 2 opérations
    N = 4 E: 4096 opérations F: 24 opérations
    N = 8 E: 16'777'216 opérations F: 40'320 opérations
    N = 10 E: 1'073'741'824 opérations F: 3'628'800 opérations
    N = 12 E: 68'719'476'736 opérations F: 479'001'600 opérations
    On voit que N! croit plus vite que 8N. A partir d'un nombre Nc, l'algorithme E est plus rapide. (Nc=20)