📌 Algorithmes de Tri sur les Tableaux
1️. Tri à Bulles (Bubble Sort)
Le tri à bulles compare les éléments adjacents et les échange si nécessaire, jusqu'à ce
que le tableau soit trié.
I=0 j=0
T[j]>T[j+1]
Perm
9 2 9 4 1
9 2 9 4 1
9 1 4
Algorithme TriBulles
Début
Pour i allant de 1 à N-1 faire
Pour j allant de 1 à N-i faire
Si Tableau[j] > Tableau[j+1] Alors
Échanger Tableau[j] et Tableau[j+1]
Fin Si
Fin Pour
Fin Pour
Fin
2️ Tri par Sélection (Selection Sort)
Le tri par sélection trouve l’élément minimum
et le place à sa position correcte.
5 3 4
I=1 j=2 min=1 T[min]>T[j]
Min=2 j=3
Temp=T[i]
T[i]=T[min]
T[min]=Temp
3 5 4
I=2
Min=2 j=3
Min=3
Algorithme TriSelection
Début
Pour i allant de 1 à N-1 faire
Min ← i
Pour j allant de i+1 à N faire
Si Tableau[j] < Tableau[Min] Alors
Min ← j
Fin Si
Fin Pour
Échanger Tableau[i] et Tableau[Min]
Fin Pour
Fin
3️ Tri par Insertion (Insertion Sort)
Le tri par insertion insère chaque élément à sa place en décalant les valeurs
supérieures.
1 6 8 5
1 5 6 8
I=2 cle=6 j=1
I=3 cle=8 j=2
I=4 cle=5 j=3
Algorithme TriInsertion
Début
Pour i allant de 2 à N faire
Clé ← Tableau[i]
j ← i-1
Tant que j > 0 et Tableau[j] > Clé faire
Tableau[j+1] ← Tableau[j]
j ← j-1
Fin Tant que
Tableau[j+1] ← Clé
Fin Pour
Fin
📌 Complexité : O(n²), mais efficace sur de petits ensembles de données.
📌 Cours : Complexité des Algorithmes
1️. Introduction à la Complexité
La complexité algorithmique mesure les ressources nécessaires à l’exécution d’un
algorithme, notamment en temps et en mémoire.
Elle permet de comparer l’efficacité de différents algorithmes pour résoudre un même
problème.
👉 Types de Complexité :
Complexité en temps : Mesure le nombre d'opérations nécessaires en fonction de
la taille des données.
Complexité en espace : Évalue la quantité de mémoire utilisée par l’algorithme.
2️Notations de la Complexité
Les notations asymptotiques permettent de décrire la croissance du temps
d’exécution d’un algorithme en fonction de la taille des entrées.
👉 Notation O (Grand O)
Représente la borne supérieure de la complexité.
Exprime le pire cas d’exécution.
Exemple : O(n²) signifie que le temps d'exécution croît au plus comme n².
👉 Notation Ω (Omega)
Représente la borne inférieure de la complexité.
Exprime le meilleur cas d’exécution.
Exemple : Ω(n) signifie que l'algorithme prend au moins un temps proportionnel à
n.
👉 Notation Θ (Thêta)
Représente une borne moyenne de la complexité.
Exemple : Θ(n log n) signifie que l’algorithme a une complexité comprise entre
O(n log n) et Ω(n log n).
3️Principales Complexités
Complexité Description Exemple
Temps d'exécution indépendant Accès direct à un élément d’un
O(1) (Constante)
de la taille des données. tableau
O(log n) Réduit de moitié la taille du
Recherche dichotomique
(Logarithmique) problème à chaque étape.
Temps proportionnel à la taille
O(n) (Linéaire) Parcours d’un tableau
des données.
Complexité typique des Tri Fusion, Tri Rapide (cas
O(n log n)
algorithmes de tri efficaces. moyen)
Croissance rapide, inefficace
O(n²)
pour de grands ensembles de Tri par sélection, Tri à bulles
(Quadratique)
données.
Temps double à chaque Algorithmes de backtracking (ex :
O(2ⁿ)
augmentation de la taille des Problème du voyageur de
(Exponentielle)
données. commerce)
4️ Exemples d'Analyse de Complexité
I=1 …………1
I=I+1…………2
J=j*2………….2
👉 Ex. 1 : Boucle simple (Complexité O(n))
Algorithme Exemple1
Début
Pour i allant de 1 à 5 faire
Afficher(i) …………1
Fin Pour
Fin
O(5)
Algorithme Exemple1
Début
Pour i allant de 1 à N faire
Afficher(i) ………..1
Afficher(i) ………..1
Fin Pour
Fin
O(2N)=O(N)
📌 Analyse : La boucle exécute N itérations → O(n).
👉 Ex. 2 : Boucle imbriquée (Complexité O(n²))
Algorithme Exemple2
Début
Pour i allant de 1 à N faire
Pour j allant de 1 à N faire
Afficher(i, j) ………….1 N N
Fin Pour
Fin Pour
Fin
O(N*N)=O(n2)
Si(T[i]<T[i+1) alors ….2
J=2+j; … 2
3
Ecrire()…..1
Sinon
Ecrire()…..1 1
O(2+max(3,1))=O(5)=O(1)
📌 Analyse : Deux boucles imbriquées, donc N × N opérations → O(n²).
👉 Ex. 3 : Recherche dichotomique (Complexité O(log n))
Algorithme RechercheDichotomique(Tableau, Gauche, Droite, X)
Début
Tant que Gauche ≤ Droite faire
Milieu ← (Gauche + Droite) / 2
Si Tableau[Milieu] = X Alors
Retourner Milieu
Sinon Si Tableau[Milieu] < X Alors
Gauche ← Milieu + 1
Sinon
Droite ← Milieu - 1
Fin Tant que
Retourner -1
Fin
📌 Analyse : À chaque itération, on divise la recherche par 2 → O(log n).
5️. Optimisation des Algorithmes
Val=13
2 4 6 8 9 10 13
2 4 6 8 9 10 13
2 410 6 813
👉 Quelques techniques d’optimisation :
1. Éviter les boucles inutiles : Réduire le nombre de comparaisons et d’itérations.
2. Utiliser des structures de données efficaces : Par exemple, un tableau trie
permet une recherche plus rapide qu’une liste non triée.
3. Diviser pour régner : Appliquer la décomposition du problème (ex : Tri Fusion,
Recherche dichotomique).
4. Exercices d’Application
5. ✍️Exercice 1 : Analyser la complexité de l'algorithme suivant :
Algorithme Exemple3
Début
Pour i allant de 1 à N faire
j←1
Tant que j < N faire
Afficher(i, j) …1
j←j*2 …2
Fin Tant que
Fin Pour
Fin
➡ Question : Quelle est la complexité de cet algorithme ?
Au départ, It0 : j=1 20
Après la première itération de la boucle interne, j devient 2. It1:j=2 21
Après la deuxième itération, j devient 4. It2 j=4 22
It3 j=8 23
It4 j=16 2
.
.
Itk j=2k
où k est le nombre d'itérations de la boucle interne. La boucle continue tant que j < N.
Donc, la condition de terminaison de la boucle interne est :
2k ≥N
k=log2(N)
O(log2(N))
La boucle interne effectue log₂ N itérations, ce qui donne une complexité O(log N)
pour cette boucle.
👉 2. Ignorer les constantes
O(5n) = O(n) → On ne garde que le facteur dominant.
📌 Exercice 1 : Analyse de Complexité
Considérons l’algorithme suivant :
Algorithme Exo1(Tableau, n)
Début
Pour i allant de 1 à n faire
x←x+1
Fin Pour
j←1
Tant que j < n faire
j←j*2
Fin Tant que
Fin
Questions :
1. Déterminer la complexité de chaque boucle séparément.
2. Trouver la complexité totale et l’écrire sous la notation O().
📌 Exercice 2 : Somme de Complexités
On a deux parties dans un algorithme avec les complexités suivantes :
Partie A : O(n²)
Partie B : O(n log n)
Questions :
1. Quelle est la complexité finale de l’algorithme contenant ces deux parties ?
📌 Exercice 3 : Boucles Imbriquées
Considérons le code suivant :
Algorithme Exo3(n)
Début
Pour i allant de 1 à n faire
Pour j allant de 1 à log(n) faire
x←x+1
Fin Pour
Fin Pour
Fin
Questions :
1. Quelle est la complexité de la boucle interne ?
2. Quelle est la complexité de la boucle externe ?
3. Quelle est la complexité totale de l’algorithme ?
📌 Exercice 4 : Recherche et Complexité
Un algorithme contient trois étapes avec les complexités suivantes :
Étape 1 : O(n)
Étape 2 : O(log n)
Étape 3 : O(n²)
Questions :
1. Quelle est la complexité globale de l’algorithme ?
📌 Exercice 5 : Analyse d’un Algorithme Récursif
Algorithme Exo5(n)
Début
Si n ≤ 1 alors
Retourner 1
Sinon
Retourner Exo5(n/2) + Exo5(n/2)
Fin
🔹 Exercice 6
Début
i←N
Tant que i > 1 faire
Afficher(i)
i←i/2
Fin Tant que
Fin
➡ Question : Quelle est la complexité de cet algorithme ?
🔹 Exercice 7 :
Début
Pour i allant de 1 à N faire
j←N
Tant que j > 1 faire
Afficher(i, j)
j←j/2
Fin Tant que
Fin Pour
Fin
➡ Question : Quelle est la complexité de cet algorithme ?
Exercice 8
Début
j←1
Tant que j < N faire
Afficher(j)
j←j*3
Fin Tant que
Fin
➡ Question : Quelle est la complexité de cet algorithme ?
🔹 Exercice 9
Début
Pour i allant de 1 à N faire
j←1
Tant que j < N faire
Afficher(i, j)
j←j*3
Fin Tant que
Fin Pour
Fin
➡ Question : Quelle est la complexité de cet algorithme ?