Université Ibn Zohr
Faculté des Sciences Appliquées
Génie Informatique et Systèmes Intelligents
Tronc Commun : Informatique Appliquée - S1
Module 113
Algorithmique 1
Présenté par :
Pr. FATEH & Pr. AHED
Année Universitaire: 2024-2025
Plan
1 Recherche d’un élément dans un tableau
Recherche séquentielle
Recherche dichotomique
2 Tri d’un tableau
Le tri par sélection
Le tri par insertion simple
Le tri à bulles
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 2 / 24
Recherche d’un élément dans un tableau
Plan
1 Recherche d’un élément dans un tableau
Recherche séquentielle
Recherche dichotomique
2 Tri d’un tableau
Le tri par sélection
Le tri par insertion simple
Le tri à bulles
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 3 / 24
Recherche d’un élément dans un tableau
Introduction
Dans ce chapitre, nous présentons des algorithmes de recherche d’un
élément dans un tableau. Deux types de recherche seront présentés : la
recherche séquentiel le qui concerne un tableau dont les éléments ne sont
pas ordonnés et la recherche dichotomique qui concerne les tableaux
ordonnés (ou triés).
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 4 / 24
Recherche d’un élément dans un tableau Recherche séquentielle
Recherche séquentielle
Principe
▶ Parcourir les éléments du tableau progressivement du début à la fin et
les comparer avec l’élément recherché x .
▶ Si le tableau n’est pas trié, arriver à la fin du tableau signifie que
l’élément n’existe pas.
▶ Dans un tableau trié de manière croissante, le premier élément trouvé
supérieur à l’élément recherché x , permet d’arrêter la recherche.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 5 / 24
Recherche d’un élément dans un tableau Recherche séquentielle
Recherche séquentielle
Version 1
Algorithme RechSéq
Variables i, ValRech : Entier
Tableau T[N] : Entier
trouvé : Booléen
Début
trouvé ← Faux ;
Pour i allant de 0 à N-1 faire
Si (T[i] = ValRech) Alors
trouvé ← Vrai ;
Écrire(ValRech," appartient au tableau") ;
Finsi
Finpour
Si (trouvé = Faux) Alors
Écrire(ValRech, " n’appartient pas au tableau") ;
Finsi
Fin
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 6 / 24
Recherche d’un élément dans un tableau Recherche séquentielle
Recherche séquentielle
Version 2
Algorithme RechSéq
Variables i, ValRech : Entier
Constant N=20
Tableau T[N] : Entier
Début
I ← 0;
TantQue (T[i] <> ValRech ET I<N)faire
i ← i+1
FinTantQue
Si (I>=N) Alors
Écrire(ValRech," n existe pas dans le tableau") ;
Sinon
Écrire(ValRech, " est un élément du tableau") ;
Finsi
Fin
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 7 / 24
Recherche d’un élément dans un tableau Recherche dichotomique
Recherche dichotomique
Introduction
La recherche dichotomique d’un élément dans un tableau est utilisée pour la
recherche d’un élément dans un tableau ordonné ou trié.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 8 / 24
Recherche d’un élément dans un tableau Recherche dichotomique
Recherche dichotomique
Principe
Principe : diviser par 2 le nombre d’éléments dans lesquels on cherche la
valeur x à chaque étape de la recherche. Pour cela on compare x avec
T[milieu] :
1 Si x < T[milieu], il suffit de chercher x dans la 1ère moitié du tableau
entre (T[0] et T[milieu-1])
2 Si x > T[milieu], il suffit de chercher x dans la 2ème moitié du
tableau entre (T[milieu+1] et T[N-1])
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 9 / 24
Recherche d’un élément dans un tableau Recherche dichotomique
Algorithme Recherche
Variables inf, sup, milieu, ValRech : Entier
Tableau T[N] : Entier
trouvé : Booléen
Début
inf ← 0 ;
sup ← N - 1 ;
trouvé ← Faux ;
Tant que (inf <= sup) ET (trouvé = Faux) faire
milieu ← (inf + sup) div 2 ;
Si (T[milieu] = ValRech) Alors
trouvé ← Vrai ;
Sinon Si (ValRech > T[milieu]) Alors
inf ← milieu + 1 ;
Sinon
sup ← milieu - 1 ;
Finsi
Fintantque
Si trouvé = Vrai Alors
Écrire(ValRech, " appartient au tableau") ;
Sinon
Écrire(ValRech, " n’appartient pas au tableau") ;
Finsi
Fin
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 10 / 24
Recherche d’un élément dans un tableau Recherche dichotomique
Recherche dichotomique
Exemple d’exécution
▶ Considérons le tableau T :
4 6 10 15 17 18 24 27 30
▶ Si la valeur cherché est 20 alors les indices inf, sup et milieu vont
évoluer comme suit :
inf 0 5 5 6
sup 8 8 5 5
milieu 4 6 5
▶ Si la valeur cherché est 10 alors les indices inf, sup et milieu vont
évoluer comme suit :
inf 0 0 2
sup 8 3 3
milieu 4 1 2
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 11 / 24
Tri d’un tableau
Plan
1 Recherche d’un élément dans un tableau
Recherche séquentielle
Recherche dichotomique
2 Tri d’un tableau
Le tri par sélection
Le tri par insertion simple
Le tri à bulles
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 12 / 24
Tri d’un tableau
Tri d’un tableau
▶ Le tri consiste à ordonner les éléments du tableau dans l’ordre croissant
ou décroissant
▶ Il existe plusieurs algorithmes connus pour trier les éléments d’un
tableau :
1 Le tri par sélection
2 Le tri par insertion simple
3 Le tri à bulles
▶ Nous verrons dans la suite l’algorithme de tri par sélection, l’algorithme
de tri par insertion simple et l’algorithme de tri à bulles. Le tri sera
effectué dans l’ordre croissant
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 13 / 24
Tri d’un tableau Le tri par sélection
Le tri par sélection
Le tri par sélection est un algorithme de tri qui fonctionne en trouvant à
chaque étape le plus petit élément du tableau non trié et en l’échangeant
avec l’élément en cours. Il est facile à comprendre mais peu efficace pour
trier de grandes quantités de données, car il compare chaque élément avec
tous les autres, ce qui prend beaucoup de temps.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 14 / 24
Tri d’un tableau Le tri par sélection
Le tri par sélection
Principe
le principe du tri par sélection est le suivant :
▶ rechercher le plus petit élément du tableau, et l’échanger avec
l’élément d’indice 0 ;
▶ rechercher le second plus petit élément dutableau, et l’échanger avec
l’élément d’indice 1 ;
▶ continuer de cette façon jusqu’à ce que le tableau soit entièrement trié.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 15 / 24
Tri d’un tableau Le tri par sélection
Le tri par sélection : Exemple d’exécution
▶ Soit le tableau T suivant composé de 5 entiers :
▶ Étape 1 : on cherche le plus petit parmi les 5 éléments du tableau. On
l’identifie en troisième position, et on l’échange alors avec l’élément 1 :
▶ Étape 2 : on cherche le plus petit élément, mais cette fois à partir du
deuxième élément. On le trouve en dernière position, on l’échange avec
le deuxième :
▶ Étape 3 : Le tableau est trié par ordre croissant
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 16 / 24
Tri d’un tableau Le tri par sélection
Le tri par sélection
Algorithme
▶ Supposons que le tableau est noté T et sa taille N
Pour i allant de 0 à N-2 faire
min ← i ;
Pour j allant de i+1 à N-1 faire
Si (T[j] < T[min]) alors
min ← j ;
Finsi
FinPour
Si (min <> i) alors
temp ← T[min] ;
T[min] ← T[i] ;
T[i] ← temp ;
FinSi
FinPour
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 17 / 24
Tri d’un tableau Le tri par insertion simple
Le tri par insertion simple
Principe
Le tri par insertion est un algorithme de tri simple mais efficace pour les
petites tailles de données. Il fonctionne de manière similaire à la façon dont
on trie des cartes dans la main :
1 On commence par considérer le premier élément de la liste comme trié.
2 Puis, pour chaque élément suivant, on le compare aux éléments déjà
triés et on l’insère à la bonne position.
3 L’algorithme répète ce processus jusqu’à ce que tous les éléments
soient triés.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 18 / 24
Tri d’un tableau Le tri par insertion simple
Le tri par insertion simple
Algorithme Tri_Insertion
Variables i, j, temp : Entier
Tableau T[N] : Entier
Début
Pour i allant de 1 à N-1 faire
temp ← T[i] ;
j ← i;
Tant que (j > 0 et T[j-1] > temp) faire
T[j] ← T[j-1] ;
j ← j - 1;
Fintantque
T[j] ← temp ;
Finpour
Fin
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 19 / 24
Tri d’un tableau Le tri par insertion simple
Le tri par insertion simple
Description
Le tableau suivant montre le fonctionnement de cet algorithme.
T[0] T[1] T[2] T[3] T[4] T[5] Echange
7 4 1 2 9 5 4
4 7 1 2 9 5 1
1 4 7 2 9 5 2
1 2 4 7 9 5 9
1 2 4 7 9 5 5
1 2 4 5 7 9
Chaque ligne indique le contenu du tableau T après chaque itération de la
boucle Pour, et la valeur conservée par la variable Echange.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 20 / 24
Tri d’un tableau Le tri à bulles
Le tri à bulles
Principe
Soit T un tableau d’entiers. Le tri à bulles consiste à :
1 Comparer, deux à deux, les éléments consécutifs d’un tableau ( T[i] et
T[i+1]).
2 Effectuer une permutation si T[i] > T[i+1].
3 On continue de trier jusqu’à ce qu’il n’y ait plus de permutation.
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 21 / 24
Tri d’un tableau Le tri à bulles
Algorithme Tri_Bulle
Variables i, N, echange : Entier
Tableau T[N] : Entier
Permut : Booleen
Début
Répéter
Permut←faux
Pour i allant de 0 à N-2 faire
Si (T[i] > T[i+1]) alors ;
echange ← T[i]
T[i] ← T[i+1]
T[i+1] ← echange
Permut ← vrai
FinSI
Finpour
Jusqu’a (Permut=faux)
Fin
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 22 / 24
Tri d’un tableau Le tri à bulles
Exemple d’exécution
Exemple d’exécution
Soit le tableau T suivant composé de 5 entiers :
indice 0 1 2 3 4
T[i] 60 50 20 40 30
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 23 / 24
Tri d’un tableau Le tri à bulles
Travaux Dirigés N°4
Pr. FATEH & Pr. AHED (FSA) M113 2024-2025 24 / 24