Informatique II - Travaux Pratiques

Série d'exercices no 6

Exercice 6-1 : Tri par bulles

Compter le nombre de comparaisons nécessaures.

Qu'est-ce qu'il se passe quand la liste est 2 fois plus longue?

Exercice 6-2 : Tri par fusion

Décrire les différentes étapes du tri par fusion récursif dont l'algorithme est donné ci-dessous. Appliquer donc à la main l'algorithme au tableau T et montrer quelles sont les étapes intermédiaires avant le tri final.

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

ALGORITHME :

// separation de la liste un 2 parties (noter la boucle recursive)

// notons n=taille_tableau



Tri_par_fusion(T[1,...,n] {
	Si n>1 {
	Tri_par_fusion(T[1,...,n/2]);
	Tri_par_fusion(T[(n/2)+1,...,n];
	Fusion(T,n,n/2); }
} 



// l'algo de fusion 



fusion(T,taille_tableau,index_milieu_tableau) {
	i=1;
	j=index_milieu_tableau+1;
	k=1;
	
//Fusion des deux parties du tableau et tri dans le tableau temporaire U

	Tant que (i<=index_milieu_tableau) et que (j<=taille_tableau) faire {
	Si (T[i]<=T[j]) {
		U[k] = T[i];
		i=i+1; }

	Sinon {
		U[k] = T[j];
		j=j+1; }
}

// Quand une des deux parties est traiteé, les éléments restants sont mis à la suite 

	Si (i>index_milieu_tableau) {
		Pour L=j à taille_tableau faire {
		U[k]=T[L];
		k=k+1; }
	}

	Si (j>taille_tableau) {
		Pour L=i à index_milieu_tableau faire {
		U[k]=T[L];
		k=k+1;}
	}

// Copie du tableau U dans T

	Pour i=1 à taille_tableau faire {
	T[i]=U[i]; }
} end fusion

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

Expliquer pourquoi le tri par fusion a une complexité de O(nlog(n)). Utiliser un exemple concret d'une liste de 16 éléments et compter les opérations de comparaison.

La complexité du tri par bulle est O(n²). Comparer le temps de calcul des 2 algorithmes de tri par bulles et par fusion avec une liste de 128 éléments.

Exercice 6-4 : Ordres de complexité

1. Soit 2 programmes A et B qui utilisent 2 algorithmes différents pour résoudre le même problème, à savoir trier une liste de N objets.

   Le programme A a besoin d'un temps t = 10 000 * N pour trier la liste.
   Le programme B a besoin d'un temps t = 2 * N² pour trier la même liste.
   

   1. Quel programme est plus rapide pour trier une liste de 5 objets?
   2. Quel est la longueur critique N_c telle que pour tout N > N_c, le programme A est plus rapide que le B?
   3. Comparer les performances des programmes A et B avec un troisième programme C qui trie la liste en un temps t = 10 + 0.5 * N³.

2. Soit 2 programmes E et F qui utilisent 2 algorithmes différents pour trier une liste de N objets.

   Le programme E a besoin d'un temps t = 8^N.
   Le programme F a besoin d'un temps t = N!.
   

   Quel programme est plus rapide? Discuter les les cas où N = 2,4,8,10,12.