Scribd
Importer
155 vues4 pages

TD4 Algorithmique

Ce document présente quatre exercices sur les algorithmes de recherche et de tri. Le premier exercice demande d'écrire des algorithmes pour trier les diagonales principales d'une matrice carrée. Le deuxième exercice concerne l'implémentation d'une fonction de recherche dichotomique dans un tableau trié. Le troisième exercice porte sur le tri à bulles d'un tableau donné. Le quatrième exercice demande de décrire un algorithme de tri par insertion dichotomique.

Transféré par

Marwan Ghazali
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
155 vues4 pages

TD4 Algorithmique

Ce document présente quatre exercices sur les algorithmes de recherche et de tri. Le premier exercice demande d'écrire des algorithmes pour trier les diagonales principales d'une matrice carrée. Le deuxième exercice concerne l'implémentation d'une fonction de recherche dichotomique dans un tableau trié. Le troisième exercice porte sur le tri à bulles d'un tableau donné. Le quatrième exercice demande de décrire un algorithme de tri par insertion dichotomique.

Transféré par

Marwan Ghazali
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Tronc Commun

Module : Algorithmique

Travaux Dirigés

Pr. Nabila ZRIRA


Département Informatique

Année Universitaire : 2021-2022


Travaux Dirigés Tronc Commun
Algorithmique Année : 2021 - 2022

TD 4 : Les algorithmes de recherche et tri

Exercice 1

En utilisant l’algorithme de tri par sélection et une matrice M réelle carrée n x n :


1- Ecrire un algorithme pour trier la première diagonale principale dans l’ordre croissant
(dans le sens croissant de l’indice des lignes).
2- Ecrire un algorithme pour trier la deuxième diagonale principale dans l’ordre croissant
(dans le sens croissant de l’indice des lignes).

Exercice 2

Implémenter une fonction, de complexité optimale, qui prend en paramètre un tableau trié T, sa
taille n et un élément e et qui renvoie -1 si l’élément e n’existe pas dans le tableau ou qui renvoie
la position de sa première occurrence s’il existe. Tester l’algorithme avec le tableau
T=[1,3,3,5,6,7,7] et la valeur e=3.

Exercice 3

On considère le tableau T suivant :

0 1 2 3 4 5 6 7 8
T: 2 3 10 7 5 12 13 27 14

1- En utilisant le principe de l’algorithme tri à bulles que vous avez déjà vu en cours,
essayez de trier le tableau T.
2- Après combien d’itérations le tableau T devient trié ?
3- Sachant que le nombre total d’itérations nécessaire pour trier n’importe quel tableau de
𝑁(𝑁−1)
taille N éléments est itérations, déduire le problème de la version basique du tri
2
à bulles.
4- Proposez une amélioration de l’algorithme du tri à bulles.

Pr. Nabila ZRIRA Page 2 sur 4


Travaux Dirigés Tronc Commun
Algorithmique Année : 2021 - 2022

Algorithme du tri à bulles basique


Fonction Tri_bulle(T Tableau en Réel, n en Entier)
Début
Variables i, j en Entier
Variable Temp en Réel
Pour i  1 à n-1 faire
Pour j  0 à n-1-i faire
Si T[j] > T[j+1] alors
Temp  T[j]
T[j]  T[j+1]
T[j+1]  Temp
Finsi
FinPour
FinPour
Fin

Exercice 4 : Tri par insertion dichotomique

Donnez un algorithme pour :


1- Saisir les données d’un tableau T composé de n entiers.
2- Trier les données du tableau T dans l’ordre croissant par la méthode du tri par insertion
dichotomique.
3- Afficher les données du tableau T trié dans l’ordre croissant.
4- Donnez l’ordre de grandeur du nombre d’itérations effectuées par l’algorithme du tri
par insertion dichotomique pour trier le tableau T composé de n entiers.
La méthode du tri par insertion dichotomique :
On veut améliorer le tri par insertion. Au lieu de commencer la comparaison du début de la
portion du tableau qui est en ordre, on va faire une comparaison dichotomique.
On suppose que les (i-1) premiers éléments sont triés dans l’ordre croissant. On cherche par la
suite à insérer l’élément T[i] à sa position dans la portion triée (1 ≤ p ≤ (i−1)), de la façon
suivante :

• On compare T[i] avec la valeur de l’élément du milieu, T[m], de la partie en ordre


• Si T[i] est supérieur strictement à T[m] on refait l’opération dans le tableau d’intervalle
[m+1, d].
• Si T[i] est inférieur ou égale à T[m] on refait l’opération dans le tableau d’intervalle
[g,m−1].
• La première fois, la partie en ordre est composée d’un seul élément T[0].

Pr. Nabila ZRIRA Page 3 sur 4


Travaux Dirigés Tronc Commun
Algorithmique Année : 2021 - 2022

i-1 i

Pr. Nabila ZRIRA Page 4 sur 4

Vous aimerez peut-être aussi