Algorithmique et Python
Pr. GABLI MOHAMMED
medgabli@yahoo
MIP + Actuariat
FS-Oujda
2023-2024
Algorithmique et Python
PLAN
• Introduction à l'algorithmique
• Instructions élémentaires (Variable, E/S, …)
• Structures conditionnelles
• Structures répétitives
• Tableau
• Algorithmes de tri et de recherche
• Initiation au langage Python
29/10/2023 GABLI - 2023 2
Cours, TD et TP
Voir les deux sites:
1. [Link]
2. [Link]
Les tableaux
Rappel
Algorithme: Note
Variables: i : Entier
Tableau Note[12]: Double
Debut
Pour i ← 0 à 11 Faire
Ecrire (Entrer une note);
Lire ( Note[i] )
FinPour
Fin
GABLI - 2011 4
Les tableaux
Rappel (chercher le plus petit élément)
Algorithme: PlusPetitElement
Variables: i, min, posMin : Entier
Tableau T[7]: entier
Debut
min ← T[0] ;
posMin ← 0 ;
Pour i ← 1 à 6 Faire
Si (min > T[i]) Alors
min = T[i] ;
posMin = i ;
FinSi
FinPour
Fin
GABLI - 2011 5
Algorithme d’échange (Rappel)
La partie de l’algorithme qui permute (échange) les
deux éléments: t[i] et t[j]
temp ← t[i]
t[i] ← t[j]
t[j] ← temp
GABLI - 2011 6
Algorithmes de tri
• Lorsque le type des éléments d’un tableau possède
un ordre total, on peut les ranger en ordre croissant
ou décroissant; on dit qu’on a trié le tableau;
• Il existe plusieurs méthodes de tri qui se
différencient par leur complexité d’exécution et leur
complexité de compréhension pour le
programmeur.
• Dans ce cours, on étudiera le tri par sélection, le tri
à bulle et le tri par insertion.
GABLI - 2011 7
Tri par sélection
Principe
Pour chaque entier j (j de 0 à n-1) :
• parcourir les éléments T [j], T [j + 1], . . ., T [n-1],
• retenir l’indice k du plus petit élément.
• placer au rang j le plus petit élément (en
échangeant T [j] et T [k]).
GABLI - 2011 8
Tri par sélection
Exemple
5 3 7 2 8 1 9
1 3 7 2 8 5 9
1 2 7 3 8 5 9
1 2 3 7 8 5 9
1 2 3 5 8 7 9
1 2 3 5 7 8 9
1 2 3 5 7 8 9
GABLI - 2011 9
Tri par sélection
Algorithme: Tri par sélection
Variables: i, j, indmin : Entier
Tableau T[n]: entier
Debut
Pour i de 0 à n – 2 Faire
indmin ← i
Pour j de i + 1 à n - 1 Faire
Si t[j] < t[indmin] Alors
indmin ← j
FinSi
FinPour
Si indmin ≠ i, Alors
échanger t[i] et t[indmin]
FinSi
FinPour
Fin
GABLI - 2011 10
Tri par sélection
(suite)
avec échanger t[i] et t[indmin]:
temp ← t[i]
t[i] ← t[indmin]
t[indmin] ← temp
Remarque
Le tri par sélection est un algorithme simple, mais il est
considéré comme inefficace à cause de sa complexité élevée
(temps d’exécution, vous verrez la complexité plus loin).
GABLI - 2011 11
Tri à bulle
Principe
• Le tri à bulle consiste à parcourir le tableau en
comparant les éléments côte à côte et en les
permutant s'ils ne sont pas dans le bon ordre.
• On s'arrête dès que l'on détecte que le tableau est
trié : si aucune permutation n'a été faite au cours
d'une passe.
GABLI - 2011 12
Tri à bulle
Exemple
5 3 7 2 8
3 5 7 2 8
3 5 7 2 8
3 5 2 7 8
3 5 2 7 8
On a fini la première passe, le tableau n’est pas
encore trié, donc on passe à la deuxième passe.
GABLI - 2011 13
Tri à bulle
Exemple
3 5 2 7 8
3 5 2 7 8
3 2 5 7 8
3 2 5 7 8
3 2 5 7 8
On a fini la deuxième passe, le tableau n’est pas
encore trié, donc on passe à la troisième passe.
GABLI - 2011 14
Tri à bulle (Exemple)
3 2 5 7 8
2 3 5 7 8
2 3 5 7 8
2 3 5 7 8
2 3 5 7 8
Le tableau est maintenant trié, donc on s’arrète.
GABLI - 2011 15
Tri à bulle (premier algorithme)
Algorithme: Tri_a_bulle
Variables: i, j : Entier
Tableau T[n]: entier
Debut
Pour i de n−1 à 1 Faire
Pour j de 0 à i − 1 Faire
Si T [j] > T [j + 1] Alors
échanger T [j] et T [j + 1]
FinSi
FinPour
FinPour
Fin
Remarque: cet algorithme finit le nombre d’itérations même si
le tableau est trié.
GABLI - 2011 16
Tri à bulle (deuxième algorithme)
Algorithme: Tri_a_bulle
Variables: i, j, passage : Entier
permut: booléan
Tableau T[n]: entier
Debut
passage ← 0
Répéter
permut ← FAUX
Pour i de 0 à n-2-passage Faire
Si T[i] > T[i+1] Alors
echanger T[i] et T[i+1]
permut ← VRAI
FinSi
FinPour
passage ← passage + 1
Jusqu’à permut = FAUX
Fin GABLI - 2011 17
Tri par insertion
Principe
• Ordonner les deux premiers éléments du tableau
• Insérer le 3ème élément de manière à ce que les 3
premiers éléments soient triés
• Insérer le 4ème élément à “sa” place pour que les 4
premiers éléments soient triés
• ...
• Insérer le nème élément à sa place.
Remarque
A la fin de la ième itération, les i premiers éléments sont
triés et rangés au début du tableau.
GABLI - 2011 18
Tri par insertion (Exemple)
5 3 7 2 8
3 5 7 2 8
3 5 7 2 8
2 3 5 7 8
3 5 2 7 8
L’insertion du 2 se fait en comparant d’abord 2
et 7, puis 2 et 5 et enfin 2 et 3.
GABLI - 2011 19
Tri par insertion
Algorithme: Tri_par_insertion
Variables: i, j, x : Entier
Tableau T[n]: entier
Debut
pour i de 1 à n-1 Faire
# mémoriser T[i] dans x
x ← T[i]
# décaler les éléments T[0]..T[i-1] qui sont plus grands
que x, en partant de T[i-1]
j←i
Tant que ( j > 0 et T[j - 1] > x) Alors
T[j] ← T[j - 1]
j←j-1
FinTQ
T[j] ← x
FinPour
Fin
GABLI - 2011 20
