Algorithmes - Les indispensables
Les indispensables
Les indispensables sont ... indispensables 😂
I. Recherche dichotomique⚓︎
Mon info
La recherche dichotomique permet de rechercher un entier dans une liste triée, ainsi que sa position.
Quel est le principe de la dichotomie ? réfléchir avant de cliquer 😊
Le principe de la recherche dichotomique d'un entier v dans une liste triée de n éléments est le suivant :
- Si
vest égal à l'élément se trouvant au milieu de la liste liste[milieu] , l'entiervest trouvé, et on renvoie sa position. - Sinon si
v<liste[milieu], on recommence la recherche dans la première moitié de la liste :liste[0 -> milieu-1] - Sinon on recommence la recherche dans la seconde moitié de la liste :
liste[milieu + 1 -> fin]
Exercice 1 : Appartenance par dichotomie
Compléter la fonction dichotomie qui prend en paramètre une liste Python nombres et un valeur cible. Cette fonction renvoie True si cible est dans nombres et False sinon.
###
# Testsbksl-nlassert dichotomie([1, 2, 3, 4], 2)bksl-nlassert dichotomie([1, 2, 3, 4], 1)bksl-nlassert dichotomie([1, 2, 3, 4], 4)bksl-nlassert dichotomie([1, 2, 3, 4], 5) is Falsebksl-nlassert dichotomie([1, 2, 3, 4], 0) is Falsebksl-nlassert dichotomie([1, 2, 5, 6], 4) is Falsebksl-nlassert dichotomie([1], 1)bksl-nlassert dichotomie([1], 0) is Falsebksl-nlassert dichotomie([], 1) is Falsebksl-nlbksl-nlbksl-nl# Tests supplémentairesbksl-nlnombres = list(range(0, 101, 2))bksl-nlfor cible in range(101):bksl-nl assert dichotomie(nombres, cible) == (cible % 2 == 0)bksl-nlbksl-nlnombres = list(range(-100, 0, 2))bksl-nlfor cible in range(-100, 0):bksl-nl assert dichotomie(nombres, cible) == (cible % 2 == 0)bksl-nlbksl-nlnombres = list(range(-12, 10, 3))bksl-nlfor cible in range(-12, 10):bksl-nl assert dichotomie(nombres, cible) == (cible % 3 == 0)bksl-nlbksl-nlbksl-nlbksl-nl 5/5 Recherche par dichotomie
Il s'agit d'un algorithme classique. Le tableau pris en paramètre doit obligatoirement être trié.
À chaque itération, on se demande si la valeur centrale est égale à la cible :
- si oui, on renvoie immédiatement
True - si non, cette cible est soit :
- supérieure à la valeur centrale : il faut chercher dans la partie droite du tableau (
debut = milieu + 1) - inférieure à la valeur centrale : il faut chercher dans la partie gauche du tableau (
fin = milieu - 1)
- supérieure à la valeur centrale : il faut chercher dans la partie droite du tableau (
La zone de recherche (l'écart entre fin et debut) se réduit à chaque itération : si on finit par avoir fin < debut, c'est que la cible n'est pas dans le tableau. On sort de la boucle et renvoie False.
Nombre maximal de tours de boucles
Prenons un écart d'indice initial fin - debut égal à \(10^9\), (ce qui est quand même très grand).
Dans le pire des cas, où la cible n'est pas présente, on réalise tous les tours de boucles possibles.
- Au premier tour, on a un écart environ de \(\frac{10^9}{2}\), c'est à dire de \(5 \times 10^8\)
- Au deuxième tour, on a un écart environ de \(\frac{5 \times 10^8}{2}\) c'est à dire \(25 \times 10^7\)
- Ainsi de suite ...
- Au trentième tour, on a un écart d'environ \(\frac{10^9}{2^{30}}\) c'est à dire d'environ 1.
Ainsi, dans une liste de taille \(10^9\), en au plus environ 30 tours on sait si l'élément cible est présent.
###
# Testsbksl-nlassert dichotomie([1, 2, 3, 4], 2)bksl-nlassert dichotomie([1, 2, 3, 4], 1)bksl-nlassert dichotomie([1, 2, 3, 4], 4)bksl-nlassert dichotomie([1, 2, 3, 4], 5) is Falsebksl-nlassert dichotomie([1, 2, 3, 4], 0) is Falsebksl-nlassert dichotomie([1, 2, 5, 6], 4) is Falsebksl-nlassert dichotomie([1], 1)bksl-nlassert dichotomie([1], 0) is Falsebksl-nlassert dichotomie([], 1) is Falsebksl-nlbksl-nlbksl-nl# Tests supplémentairesbksl-nlnombres = list(range(0, 101, 2))bksl-nlfor cible in range(101):bksl-nl assert dichotomie(nombres, cible) == (cible % 2 == 0)bksl-nlbksl-nlnombres = list(range(-100, 0, 2))bksl-nlfor cible in range(-100, 0):bksl-nl assert dichotomie(nombres, cible) == (cible % 2 == 0)bksl-nlbksl-nlnombres = list(range(-12, 10, 3))bksl-nlfor cible in range(-12, 10):bksl-nl assert dichotomie(nombres, cible) == (cible % 3 == 0)bksl-nlbksl-nl# Finbksl-nlbksl-nl 5/5 Recherche par dichotomie
Il s'agit d'un algorithme classique. Le tableau pris en paramètre doit obligatoirement être trié.
À chaque itération, on se demande si la valeur centrale est égale à la cible :
- si oui, on renvoie immédiatement
True - si non, cette cible est soit :
- supérieure à la valeur centrale : il faut chercher dans la partie droite du tableau (
debut = milieu + 1) - inférieure à la valeur centrale : il faut chercher dans la partie gauche du tableau (
fin = milieu - 1)
- supérieure à la valeur centrale : il faut chercher dans la partie droite du tableau (
La zone de recherche (l'écart entre fin et debut) se réduit à chaque itération : si on finit par avoir fin < debut, c'est que la cible n'est pas dans le tableau. On sort de la boucle et renvoie False.
Nombre maximal de tours de boucles
Prenons un écart d'indice initial fin - debut égal à \(10^9\), (ce qui est très grand).
Dans le pire des cas, où la cible n'est pas présente, on réalise tous les tours de boucles possibles.
- Au premier tour, on a un écart environ de \(\frac{10^9}{2}\), c'est à dire de \(5 \times 10^8\)
- Au deuxième tour, on a un écart environ de \(\frac{5 \times 10^8}{2}\) c'est à dire \(25 \times 10^7\)
- Ainsi de suite ...
- Au trentième tour, on a un écart d'environ \(\frac{10^9}{2^{30}}\) c'est à dire d'environ 1.
Ainsi, dans une liste de taille \(10^9\), en au plus environ 30 tours on sait si l'élément cible est présent.
Exercice 2 : Appartenance et indice par dichotomie
Compléter la fonction indice qui prend en paramètre une liste Python tableau et une valeur cible. Cette fonction renvoie l'indice de cible dans tableau si cible est dans tableau et None sinon.
###
tableau = [23, 28, 29, 35, 37]bksl-nlbksl-nl# Testsbksl-nlassert indice(tableau, 23) == 0, "Erreur dans la recherche de 23"bksl-nlassert indice(tableau, 29) == 2, "Erreur dans la recherche de 29"bksl-nlassert indice(tableau, 37) == 4, "Erreur dans la recherche de 37"bksl-nlassert indice(tableau, 10) is None, "Erreur dans la recherche de 10"bksl-nlassert indice(tableau, 100) is None, "Erreur dans la recherche de 100"bksl-nlbksl-nl# Tests supplémentairesbksl-nlclass Tableau(list):bksl-nl def py-undpy-undinitpy-undpy-und(self, longueur, fonction):bksl-nl assert longueur > 1py-und000, "La longueur doit être supérieure à 1000"bksl-nl self.py-undlongueur = longueurbksl-nl self.py-undfonction = fonctionbksl-nl self.py-undcompteurpy-undlectures = 0bksl-nl self.py-undlecturespy-undmax = 100bksl-nlbksl-nl def py-undpy-undlenpy-undpy-und(self):bksl-nl return self.py-undlongueurbksl-nlbksl-nl def py-undpy-undgetitempy-undpy-und(self, i):bksl-nl if type(i) is slice:bksl-nl indices = range(py-stri.indices(self.py-undlongueur))bksl-nl return [self.py-undpy-undgetitempy-undpy-und(k) for k in indices]bksl-nl self.py-undcompteurpy-undlectures += 1bksl-nl if self.py-undcompteurpy-undlectures > self.py-undlecturespy-undmax:bksl-nl raise LookupError(f"Il faut réaliser strictement moins de {self.py-undlecturespy-undmax} lectures dans le tableau")bksl-nl return self.py-undfonction(i)bksl-nlbksl-nl def py-undpy-undsetitempy-undpy-und(self, i, x):bksl-nl raise NotImplementedError("Il est interdit de modifier les valeurs")bksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl return f"[{self.py-undfonction(0)}, {self.py-undfonction(1)}, ..., {self.py-undfonction(self.py-undlongueur - 1)}]"bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nl def py-undpy-unditerpy-undpy-und(self):bksl-nl for i in range(self.py-undlongueur):bksl-nl yield self.py-undpy-undgetitempy-undpy-und(i)bksl-nlbksl-nlbksl-nlfrom random import randrangebksl-nlbksl-nlfor test in range(10):bksl-nl # Création du grand tableaubksl-nl exposant = randrange(6, 10)bksl-nl N = 10py-strpy-strexposantbksl-nl a = randrange(2, 50)bksl-nl b = randrange(-1000, 1001)bksl-nl fonction = lambda i: a py-str i + bbksl-nl # Recherche du dernier élémentbksl-nl tableau = Tableau(N, fonction)bksl-nl attendu = N - 1bksl-nl cible = fonction(attendu)bksl-nl assert (bksl-nl indice(tableau, cible) == attendubksl-nl ), f"Erreur lors de la recherche de {cible} dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nl # Recherche d'un élément aléatoirebksl-nl tableau = Tableau(N, fonction)bksl-nl attendu = randrange(0, N - 1)bksl-nl cible = fonction(attendu)bksl-nl assert (bksl-nl indice(tableau, cible) == attendubksl-nl ), f"Erreur lors de la recherche de {cible} dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nlbksl-nl # Recherche d'un élément absentbksl-nl # à gauchebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = fonction(0) - 1bksl-nl assert indice(tableau, cible) is Nonebksl-nl # au centrebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = fonction(randrange(0, N - 1)) + (a - 1)bksl-nl assert indice(tableau, cible) is Nonebksl-nl # à droitebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = tableau[N + 1]bksl-nl assert indice(tableau, cible) is Nonebksl-nlbksl-nlbksl-nlbksl-nl 5/5 Recherche dichotomique itérative : à connaître
Il s'agit de l'algorithme de recherche dichotomique classique.
La recherche de l'indice du milieu
Le calcul de l'indice du milieu mérite toutefois quelques commentaires. Ici on propose milieu = (debut + fin) // 2.
Or, dans certains langages de programmation comme le C, la taille des entiers est limitée. Ce calcul milieu = (debut + fin) // 2 peut parfois excéder cette taille limite. En effet, si les deux indices debut et fin sont grands, leur somme debut + fin peut dépasser la valeur limite.
Dans ce cas on calcule l'indice du milieu en utilisant la largeur de l'intervalle : milieu = debut + (fin - debut) // 2.
Dans le cas présent, le problème ne se pose pas car, en Python, les entiers n'ont pas de taille limite. Toutefois, Si l'on avait manipulé des nombres flottants le problème serait apparu comme par exemple :
Exemple
🐍 Console Python
>>> debut = 2.0 ** 1023
>>> fin = 2.0 ** 1023 + 1
>>> debut + fin # dépassement de capacité
inf
>>> (debut + fin) / 2 # dépassement de capacité lors de la somme
inf
>>> debut + (fin - debut) / 2
8.98846567431158e+307
###
tableau = [23, 28, 29, 35, 37]bksl-nlbksl-nl# Testsbksl-nlassert indice(tableau, 23) == 0, "Erreur dans la recherche de 23"bksl-nlassert indice(tableau, 29) == 2, "Erreur dans la recherche de 29"bksl-nlassert indice(tableau, 37) == 4, "Erreur dans la recherche de 37"bksl-nlassert indice(tableau, 10) is None, "Erreur dans la recherche de 10"bksl-nlassert indice(tableau, 100) is None, "Erreur dans la recherche de 100"bksl-nlbksl-nl# Tests supplémentairesbksl-nlclass Tableau(list):bksl-nl def py-undpy-undinitpy-undpy-und(self, longueur, fonction):bksl-nl assert longueur > 1py-und000, "La longueur doit être supérieure à 1000"bksl-nl self.py-undlongueur = longueurbksl-nl self.py-undfonction = fonctionbksl-nl self.py-undcompteurpy-undlectures = 0bksl-nl self.py-undlecturespy-undmax = 100bksl-nlbksl-nl def py-undpy-undlenpy-undpy-und(self):bksl-nl return self.py-undlongueurbksl-nlbksl-nl def py-undpy-undgetitempy-undpy-und(self, i):bksl-nl if type(i) is slice:bksl-nl indices = range(py-stri.indices(self.py-undlongueur))bksl-nl return [self.py-undpy-undgetitempy-undpy-und(k) for k in indices]bksl-nl self.py-undcompteurpy-undlectures += 1bksl-nl if self.py-undcompteurpy-undlectures > self.py-undlecturespy-undmax:bksl-nl raise LookupError(f"Il faut réaliser strictement moins de {self.py-undlecturespy-undmax} lectures dans le tableau")bksl-nl return self.py-undfonction(i)bksl-nlbksl-nl def py-undpy-undsetitempy-undpy-und(self, i, x):bksl-nl raise NotImplementedError("Il est interdit de modifier les valeurs")bksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl return f"[{self.py-undfonction(0)}, {self.py-undfonction(1)}, ..., {self.py-undfonction(self.py-undlongueur - 1)}]"bksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl return self.py-undpy-undstrpy-undpy-und()bksl-nlbksl-nl def py-undpy-unditerpy-undpy-und(self):bksl-nl for i in range(self.py-undlongueur):bksl-nl yield self.py-undpy-undgetitempy-undpy-und(i)bksl-nlbksl-nlbksl-nlfrom random import randrangebksl-nlbksl-nlfor test in range(10):bksl-nl # Création du grand tableaubksl-nl exposant = randrange(6, 10)bksl-nl N = 10py-strpy-strexposantbksl-nl a = randrange(2, 50)bksl-nl b = randrange(-1000, 1001)bksl-nl fonction = lambda i: a py-str i + bbksl-nl # Recherche du dernier élémentbksl-nl tableau = Tableau(N, fonction)bksl-nl attendu = N - 1bksl-nl cible = fonction(attendu)bksl-nl assert (bksl-nl indice(tableau, cible) == attendubksl-nl ), f"Erreur lors de la recherche de {cible} dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nl # Recherche d'un élément aléatoirebksl-nl tableau = Tableau(N, fonction)bksl-nl attendu = randrange(0, N - 1)bksl-nl cible = fonction(attendu)bksl-nl assert (bksl-nl indice(tableau, cible) == attendubksl-nl ), f"Erreur lors de la recherche de {cible} dans un tableau de 10py-strpy-str{exposant} valeurs"bksl-nlbksl-nl # Recherche d'un élément absentbksl-nl # à gauchebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = fonction(0) - 1bksl-nl assert indice(tableau, cible) is Nonebksl-nl # au centrebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = fonction(randrange(0, N - 1)) + (a - 1)bksl-nl assert indice(tableau, cible) is Nonebksl-nl # à droitebksl-nl tableau = Tableau(N, fonction)bksl-nl cible = tableau[N + 1]bksl-nl assert indice(tableau, cible) is Nonebksl-nlbksl-nl# Finbksl-nlbksl-nlbksl-nl 5/5 Recherche dichotomique itérative : à connaître
Il s'agit de l'algorithme de recherche dichotomique classique.
La recherche de l'indice du milieu
Le calcul de l'indice du milieu mérite toutefois quelques commentaires. Ici on propose milieu = (debut + fin) // 2.
Or, dans certains langages de programmation comme le C, la taille des entiers est limitée. Ce calcul milieu = (debut + fin) // 2 peut parfois excéder cette taille limite. En effet, si les deux indices debut et fin sont grands, leur somme debut + fin peut dépasser la valeur limite.
Dans ce cas on calcule l'indice du milieu en utilisant la largeur de l'intervalle : milieu = debut + (fin - debut) // 2.
Dans le cas présent, le problème ne se pose pas car, en Python, les entiers n'ont pas de taille limite. Toutefois, Si l'on avait manipulé des nombres flottants le problème serait apparu :
Exemple
🐍 Console Python
>>> debut = 2.0 ** 1023
>>> fin = 2.0 ** 1023 + 1
>>> debut + fin # dépassement de capacité
inf
>>> (debut + fin) / 2 # dépassement de capacité lors de la somme
inf
>>> debut + (fin - debut) / 2
8.98846567431158e+307
Quelle est la complexité d'un algorithme de dichotomie ? réfléchir avant de cliquer 😊
💚 A retenir : L’algorithme de dichotomie a une complexité logarithmique de l'ordre de \(\log(n)\) pour une liste de taille \(n\).
II. Le tri par sélection⚓︎
Quel est le principe du tri par sélection ? réfléchir avant de cliquer 😊
Pour un tableau tab de taille n
📋 Texte
pour i allant de 0 à n-2
pos ← position du minimum dans tab à partir du rang
si pos ≠ i :
échanger tab[i] et tab[pos]
La fonction tri_selection
Compléter la fonction tri_selection prenant en argument un tableau et le triant en place à l'aide du tri par sélection.
###
# testsbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undselection(tableaupy-und0)bksl-nlassert tableaupy-und0 == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undselection(tableaupy-und1)bksl-nlassert tableaupy-und1 == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undselection(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und4 = []bksl-nltripy-undselection(tableaupy-und4)bksl-nlassert tableaupy-und4 == [], "Erreur avec un tableau vide"bksl-nlbksl-nl# Autres testsbksl-nltableaupy-und4 = [i for i in range(100, 0, -1)]bksl-nltripy-undselection(tableaupy-und4)bksl-nlassert tableaupy-und4 == [i for i in range(1, 101)]bksl-nlbksl-nlbksl-nlbksl-nl 5/5 ###
# testsbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undselection(tableaupy-und0)bksl-nlassert tableaupy-und0 == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undselection(tableaupy-und1)bksl-nlassert tableaupy-und1 == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undselection(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und4 = []bksl-nltripy-undselection(tableaupy-und4)bksl-nlassert tableaupy-und4 == [], "Erreur avec un tableau vide"bksl-nlbksl-nl# Autres testsbksl-nltableaupy-und4 = [i for i in range(100, 0, -1)]bksl-nltripy-undselection(tableaupy-und4)bksl-nlassert tableaupy-und4 == [i for i in range(1, 101)]bksl-nlbksl-nl# Finbksl-nlbksl-nlbksl-nl 5/5 Utiliser La fonction tri_selection
Exécuter le script suivant :
###
La liste de départ a été modifiée ...
C'est ce qu'on appelle un effet de bord.
La fonction a modifié "en place" la liste.
Résumé
- Le plus souvent, on écrit une procédure (pas de
return) pour le tri par selection. - C'est un tri "en place" qui modifie la liste elle-même.
- 👉 Vous devez mémoriser cette procédure.
Quel est la complexité d'un algorithme de tri par selection ? réfléchir avant de cliquer 😊
💚 A retenir : L’algorithme du tri par selection a une complexité quadratique de l'ordre de \(n^2\) pour une liste de taille \(n\).
III. Le tri par insertion⚓︎
Quel est le principe du tri par insertion ? réfléchir avant de cliquer 😊
Pour un tableau tab de taille n
🐍 Script Python
pour i allant de 1 à n-1
clef ← tab[i]
insérer la clef au bon endroit dans tab
La fonction tri_insertion
Compléter la fonction tri_insertion prenant en argument un tableau et le triant en place à l'aide du tri par insertion.
###
# Testsbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undinsertion(tableaupy-und0)bksl-nlassert tableaupy-und0 == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undinsertion(tableaupy-und1)bksl-nlassert tableaupy-und1 == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undinsertion(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und3 = []bksl-nltripy-undinsertion(tableaupy-und3)bksl-nlassert tableaupy-und3 == [], "Erreur avec un tableau vide"bksl-nlbksl-nl# Autres testsbksl-nltableaupy-und4 = [i for i in range(100, 0, -1)]bksl-nltripy-undinsertion(tableaupy-und4)bksl-nlassert tableaupy-und4 == [i for i in range(1, 101)]bksl-nlbksl-nl# Finbksl-nl 5/5 ###
# Testsbksl-nltableaupy-und0 = [3, 1, 2]bksl-nltripy-undinsertion(tableaupy-und0)bksl-nlassert tableaupy-und0 == [1, 2, 3], "Erreur avec [3, 1, 2]"bksl-nlbksl-nltableaupy-und1 = [1, 2, 3, 4]bksl-nltripy-undinsertion(tableaupy-und1)bksl-nlassert tableaupy-und1 == [1, 2, 3, 4], "Erreur avec [1, 2, 3, 4]"bksl-nlbksl-nltableaupy-und2 = [-2, -5]bksl-nltripy-undinsertion(tableaupy-und2)bksl-nlassert tableaupy-und2 == [-5, -2], "Erreur avec des valeurs négatives"bksl-nlbksl-nltableaupy-und3 = []bksl-nltripy-undinsertion(tableaupy-und3)bksl-nlassert tableaupy-und3 == [], "Erreur avec un tableau vide"bksl-nlbksl-nl# Autres testsbksl-nltableaupy-und4 = [i for i in range(100, 0, -1)]bksl-nltripy-undinsertion(tableaupy-und4)bksl-nlassert tableaupy-und4 == [i for i in range(1, 101)]bksl-nlbksl-nl 5/5 Utiliser La fonction tri_insertion
Exécuter le script suivant :
###
La liste de départ a été modifiée ...
C'est ce qu'on appelle un effet de bord.
La fonction a modifié "en place" la liste.
Résumé
- Le plus souvent, on écrit une procédure (pas de
return) pour le tri par insertion. - C'est un tri "en place" qui modifie la liste elle-même.
- 👉 Vous devez mémoriser cette procédure.
Quel est la complexité d'un algorithme de tri par insertion ? réfléchir avant de cliquer 😊
💚 A retenir : L’algorithme du tri par insertion a une complexité quadratique de l'ordre de \(n^2\) pour une liste de taille \(n\).