Td sur les algorithmes de tri

                                                               Td sur les algorithmes de tri

Exercice 1:

Simuler à la main algorithmes de tri vus en cours avec le tableau suivant :

T : 2   -5   0  15  -8  11 3  20  12  -5  1  -3 

Exercice 2:

Le tri par fusion :
En utilisant la technique Diviser pour régner, nous divisons un problème en sous-problèmes. Lorsque la solution à chaque sous-problème est prête, nous «combinons» les résultats des sous-problèmes pour résoudre le problème principal.

Supposons que nous devions trier un tableau T. Un sous-problème serait de trier une sous-section (sous-tableau) de ce tableau commençant à l'indice debut et se terminant à l'indice fin, notée T[debut..fin].

Un algorithme typique de Diviser pour régner résout un problème en utilisant les trois étapes suivantes :

Diviser

Si milieu est le point milieu entre debut et fin, alors nous pouvons diviser le sous-tableau T[debut..fin] en deux tableaux T[debut..milieu] et T[milieu + 1, fin].

Régner/Résoudre

Dans l'étape Régner, nous essayons de trier les sous-réseaux T[debut..milieu] et T[milieu + 1, fin]. Si nous n'avons pas encore atteint le cas de base (le sous-tableau contient un seul élément), nous divisons à nouveau ces deux sous-réseaux et essayons de les trier.

Combiner

Lorsque l'étape de conquête atteint l'étape de base et que nous obtenons deux sous-tableaux triés T[debut..milieu] et T[milieu + 1, fin] pour le tableau T[debut..milieu], nous combinons les résultats en créant un tableau trié T[debut..milieu] à partir de deux sous-réseaux triés T[debut..milieu] et T[milieu + 1, fin].

le travail demandé :

Ecrire un algorithme qui réalise le tri par fusion sur un tableau d'entiers.

Exercice 3:
Etudier la complexité des différents algorithmes de tri .