Algorithmes sur les tableaux

Les premières épreuves du bac de français édition 2025 sont pour bientôt ! Consulte les dates du bac de français, notre programme de révision accompagné de toutes nos fiches de révisions pour te préparer au mieux à ton examen 💪

Introduction :

Les tableaux sont des structures de données permettant le stockage d’un grand nombre d’éléments individuels. Nous pouvons les parcourir séquentiellement pour y rechercher des informations, les trier si nécessaire et ensuite exploiter le fait qu’ils soient triés pour optimiser nos recherches.

Parcours séquentiel de liste

Rappel

Les tableaux ou listes en Python sont des structures de données ordonnées et mutables, dont les éléments sont accessibles séquentiellement ainsi qu’individuellement via leur position dans la liste.

Nous allons nous intéresser au parcours séquentiel et à son utilité dans le cadre d’algorithmes de recherche. Nous étudierons dans un premier temps la recherche d’une occurrence sur des valeurs de type quelconque, puis nous effectuerons des recherches d’extremums et un calcul de moyenne.

Dans les trois cas notre algorithme repose sur le parcours séquentiel.

Définition

Parcours séquentiel :

Accès individuel aux éléments d’une structure donnée en les parcourant un par un et dans l’ordre.

Le parcours séquentiel est parfois appelé parcours linéaire.

Modalités de parcours

Le parcours séquentiel d’une liste s’effectue avec une boucle de type for … in .

une_liste_quelconque = [2, 99, -4, 37]

for element in une_liste_quelconque:

print(element)

On obtient l’affichage suivant :

2
99
-4
37

Rappel

Il est également possible de parcourir une liste avec une notation exploitant la position indicielle.

for index in range(len(une_liste_quelconque)):

print(une_liste_quelconque[index])

Recherche d’occurrence

Nous allons implémenter un algorithme de recherche d’occurrence.

Définition

Occurrence :

Une occurrence est l’apparition d’un élément donné dans un ensemble.

Notre liste n’étant pas triée il nous faudra obligatoirement parcourir la liste séquentiellement afin de déterminer si l’élément recherché est, ou non, présent.

Chaque élément de la liste est comparé à l’élément recherché, jusqu’à le trouver ou jusqu’à atteindre la fin de la liste.

def occurrence(valeur_recherchee, liste):

"""

Recherche d'un élément dans une liste.

Retourne True si l'élément est présent.

Retourne False si l'élément est absent.

"""

for element in liste:

if element == valeur_recherchee:

return True

return False

Testons notre code avec une liste de nombres.

nombres = [7, 99, -4, 51, 42, -34, 15]

print(occurrence(42, nombres))

# affiche True

print(occurrence(81, nombres))

# affiche False

Python est un langage à typage dynamique. Notre fonction de recherche d’occurrence fonctionne aussi avec d’autres types de données.

Nous le vérifions avec des chaînes de caractères.

prenoms = ['Jules', 'Louis', 'Victoria', 'Gabriel', 'Jade', 'Hugo', 'Louise', 'Paul', 'Alice', 'Camille']

print(occurrence('Alice', prenoms))

# affiche True

print(occurrence('Alan', prenoms))

# affiche False

Notre recherche fonctionne aussi avec des booléens.

verites = [True, False, True, True, False]

print(occurrence(True, verites))

# affiche True

print(occurrence(False, verites))

# affiche True

Nous pouvons de la même manière examiner un tuple de tuples.

duos = ((2, 0), (1, 4), (7, 2), (-1, 3), (9, -4))

print(occurrence((2,0), duos))

# affiche True

print(occurrence((0,2), duos))

# affiche False

Recherche de toutes les occurrences

Notre algorithme actuel se contente de détecter l’apparition de l’élément recherché dans la structure de donnée. On peut facilement le faire évoluer pour qu’il soit capable de nous indiquer combien de fois cet élément est présent.

def nombre_occurrences(valeur_recherchee, liste):

"""

Recherche d'un élément dans une liste.

Retourne le nombre de fois où l'élément recherché est présent dans la liste.

"""

compteur = 0

for element in liste:

if element == valeur_recherchee:

compteur += 1

return compteur

Nous vérifions son bon fonctionnement.

nombres = [7, 42, 99, -4, 51, 42, -34, 15, 42]

print(nombre_occurrences(42, nombres))

# affiche 3

print(nombre_occurrences(19, nombres))

# affiche 0

Cette fonction est également utilisable avec d’autres types de données.

print(nombre_occurrences('Louis', prenoms))

# affiche 1

print(nombre_occurrences('Sophie', prenoms))

# affiche 0

print(nombre_occurrences(True, verites))

# affiche 3

print(nombre_occurrences(False, verites))

# affiche 2

La recherche de toutes les occurrences nous oblige à parcourir l’intégralité de la liste, contrairement à notre précédente implémentation qui recherchait l’apparition du terme recherché et qui pouvait se terminer dès qu’il était trouvé, sans nécessairement parcourir la fin de la liste.

Nous allons maintenant nous intéresser à la recherche d’extremums.

Recherche d’extremums

Définition

Extremum :

Un extremum est une valeur extrême d’un ensemble de données. Le terme désigne aussi bien le minimum que le maximum de l’ensemble considéré.

Développons une fonction qui soit capable de retourner simultanément le minimum et le maximum d’une liste d’éléments.

def extremums(liste_quelconque):

"""Retourne le minimum et le maximum de la liste, dans cet ordre."""

minimum = liste_quelconque

maximum = liste_quelconque

for element in liste_quelconque:

if element < minimum:

minimum = element

if element > maximum:

maximum = element

return minimum, maximum

Vérifions que notre code produit bien le résultat attendu.

nombres = [7, 99, -4, 51, 42, -34, 15]

print(extremums(nombres))

# affiche (-34, 99)

On constate qu’il fonctionne aussi avec d’autres types de données.

prenoms = ['Jules', 'Louis', 'Victoria', 'Gabriel', 'Jade', 'Hugo', 'Louise', 'Paul', 'Alice', 'Camille']

print(extremums(prenoms))

# affiche ('Alice', 'Victoria')

verites = [True, False, True, True, False]

print(extremums(verites))

# affiche (False, True)

duos = ((2, 0), (1, 4), (7, 2), (-1, 3), (9, -4))

print(extremums(duos))

# affiche ((-1, 3), (9, -4))

Dans la mesure où les listes ne sont pas triées, la recherche d’extremums nous oblige à les parcourir en totalité.

Développons maintenant une fonction calculant la moyenne d’une liste.

Calcul de moyenne

Le calcul de la moyenne est assez proche de la recherche d’extremums, et nous oblige à nouveau à parcourir l’intégralité des éléments de la liste.

def moyenne(liste_quelconque):

total = 0

nombre_elements = len(liste_quelconque)

for element in liste_quelconque:

total += element

return total / nombre_elements

Notre fonction calcule bien la moyenne.

nombres = [7, 99, -4, 51, 42, -34, 15]

print(moyenne(nombres))

# affiche 25.142857142857142

Attention

Il n’est en revanche pas possible de calculer la moyenne d’une liste de chaînes de caractères, cette notion mathématique n’ayant pas de sens pour ce type de donnée.

Coût algorithmique

Les différents algorithmes que nous avons implémentés jusqu’à présent dans ce cours s’appuient tous, sur le parcours séquentiel de la liste, à partir du premier élément et jusqu’au dernier dans le pire des cas. Pour un nombre $n$ d’éléments dans la liste, on parcourt au plus $n$ éléments.

À retenir

Le coût algorithmique des recherches séquentielles est linéaire, de l’ordre de $n$, noté $\text{O}(n)$.

Astuce

Ces algorithmes ont été appliqués à des listes non ordonnées, alors que si nous les avions triées, nous aurions pu en tirer profit et optimiser notre code, notamment pour la recherche des extremums qui auraient été obligatoirement le premier et le dernier élément de la liste.

Nous allons étudier successivement deux algorithmes de tri : d’abord le tri par sélection et ensuite le tri par insertion.

Tri par sélection

Le tri par sélection est un algorithme de tri simple à comprendre et à mettre en œuvre.

Il repose sur des comparaisons et des échanges de positions dans la liste.

Principe du tri par sélection

On commence par rechercher le plus petit élément de la liste, qu’on échange avec celui du début de la liste, s’il n’était pas déjà au début. On répète ensuite l’opération à partir de l’élément suivant pour toute la portion restante de la liste, et ainsi de suite jusqu’à atteindre la fin de la liste.

À l’issue du traitement, la liste est entièrement triée.

Implémentation

L’implémentation du tri par sélection repose sur l’imbrication de deux boucles. La boucle extérieure parcourt la liste séquentiellement. La boucle intérieure parcourt la portion de liste restante pour en déterminer le minimum. Une permutation est ensuite effectuée si nécessaire.

def tri_selection(liste):

"""Effectue un tri par sélection de la liste fournie."""

for i in range(len(liste) -1):

pos_mini = i

for j in range(i + 1, len(liste)):

if liste[j] < liste[pos_mini]:

pos_mini = j

if pos_mini != i:

liste[pos_mini], liste[i] = liste[i], liste[pos_mini]

return liste

Nous testons le bon fonctionnement de notre code avec une liste non triée de nombres.

nombres = [7, 2, -4, 11, 0, 6]

print(tri_selection(nombres))

# affiche [-4, 0, 2, 6, 7, 11]

Astuce

Le langage Python permet d’inverser facilement les valeurs de deux variables avec la syntaxe suivante :

a, b = b, a

$$
On met à profit cette faculté pour inverser quand c’est nécessaire les valeurs comparées.

Avec d’autres langages ne permettant pas cette inversion, on doit recourir à une variable temporaire pour pouvoir procéder à l’échange de valeurs.

Terminaison et complexité

L’algorithme est composé de deux boucles for … in imbriquées. Chacune de ces boucles se terminera car les itérations de type for ou for … in ne peuvent pas produire de boucles infinies. L’algorithme se terminera donc nécessairement lorsque les deux boucles seront épuisées.

À retenir

Les boucles étant imbriquées le coût est quadratique. La complexité du tri par sélection est $\text{O}(n^{2})$.

Étudions maintenant un autre algorithme de tri qui procède par insertion.

Tri par insertion

Le tri par insertion est également un algorithme de tri simple à comprendre et à mettre en œuvre.

Principe du tri par insertion

Le principe est analogue à celui du tri d’un jeu de cartes où, au fur à mesure de son rangement en main, chaque carte parcourue est insérée à l’endroit approprié, en fonction de sa valeur parmi celles déjà triées. Cette méthode assez intuitive permet de trier simplement et rapidement un paquet de cartes.

Implémentation

def tri_insertion(liste):

"""Effectue un tri par insertion de la liste fournie."""

for i in range(1, len(liste)):

x = liste[i]

j = i

while j > 0 and liste[j - 1] > x:

liste[j] = liste[j - 1]

j -= 1

liste[j] = x

return liste

On vérifie que notre code fournit bien le résultat attendu.

nombres = [7, 2, -4, 11, 0, 6]

print(tri_insertion(nombres))

# affiche [-4, 0, 2, 6, 7, 11]

Astuce

L’incrémentation de valeur est possible avec la notation raccourcie indice += 1 qui est équivalente à la notation indice = indice + 1 .

La décrémentation est également possible sous la forme indice -= 1 qui est équivalente à indice = indice - 1 .

Notre algorithme de tri par insertion emploie cette notation plus compacte et fréquemment utilisée.

Terminaison et complexité

L’algorithme est composé de deux boucles imbriquées. La boucle externe for … in se terminera à l’épuisement des éléments de la liste. Dans la boucle interne de type while la variable j est un variant de boucle décroissant à chaque tour jusqu’à devenir nul. Chacune de ces boucles se terminant bien, l’algorithme se terminera nécessairement.

À retenir

Le coût est quadratique, la complexité temporelle de l’algorithme de tri par insertion est $\text{O}(n^{2})$.

Il existe une multitude d’algorithmes de tri dont les performances générales sont plus ou moins élevées. Ainsi certains algorithmes ont une complexité temporelle de $\text{O}(n\,\text{log}\,n)$.

Astuce

Des algorithmes globalement moins performants que d’autres en moyenne peuvent parfois s’avérer meilleurs dans certaines conditions particulières, liées notamment au niveau de non-tri initial ainsi qu’à la quantité de données devant être triées.

Ainsi la performance du tri par sélection est meilleure quand les données sont presque triées ou quand le nombre de données à trier reste modéré.

Si le tri d’une liste présente un certain coût, cette opération peut cependant permettre de réduire celui des opérations de recherche dans une liste. En particulier, la recherche dichotomique, dont le coût est réduit mais qui requiert en entrée une liste ordonnée.

Algorithme de recherche par dichotomie

Nous disposons d’une liste triée et nous désirons vérifier si un élément est présent dans cette liste.

Notre liste est un lexique de termes informatiques, triés par ordre alphabétique.

lexique = ['clavier', 'clé USB', 'disque dur', 'haut-parleur', 'imprimante', 'micro', 'moniteur', 'scanner', 'souris', 'webcam']

Le fait qu’une liste soit triée facilite grandement les recherches.

Imaginez un dictionnaire dont les mots ne seraient pas triés par ordre alphabétique : il faudrait en lire chaque page dans l’espoir de finir par trouver le mot dont on cherche la définition. C’est ce que fait notre algorithme naïf : il explore la liste, élément après élément, jusqu’à trouver ce qu’il cherche.

Avec un dictionnaire trié par ordre alphabétique, il est beaucoup plus facile et rapide de trouver un mot. Il suffit de l’ouvrir au milieu et de regarder si le mot recherché se situe sur la page recherchée. S’il ne l’est pas, l’ordre alphabétique nous permet de savoir s’il est situé dans la première ou dans la seconde moitié du dictionnaire. On choisit la moitié adaptée, que l’on sépare à nouveau en deux en son milieu, et on répète le processus jusqu’à finir par trouver le mot recherché.

C’est le principe de la recherche dichotomique.

Rappel

Les chaînes de caractères peuvent être ordonnées. De la même manière dont Python est capable d’évaluer l’expression $2 < 3$ comme vraie (True) et l’expression $4 < 3$ comme fausse (False), il est capable d’évaluer une égalité ou une inégalité entre deux chaînes de caractères, sur la base de l’ordre alphabétique, également appelé ordre lexicographique. Ainsi l’expression $\text{clavier} < \text{imprimante}$ est vraie (True) mais l’expression $\text{webcam} < \text{souris}$ est fausse (False).

Cette capacité du langage à comparer l’ordre lexicographique des chaînes de caractères nous permet d’implémenter facilement la recherche dichotomique.

À retenir

Nous allons à chaque fois déterminer l’élément situé au milieu de la portion de liste qui nous intéresse.
Nous commencerons par la liste complète. Si la valeur de la liste en son milieu correspond à l’élément recherché, nous l’avons trouvé et l’algorithme se termine. Sinon nous comparons la valeur de l’élément milieu avec celui que nous recherchons pour déterminer quelle moitié de liste conserver :

si l’élément milieu est supérieur dans l’ordre lexicographique au mot recherché, nous conservons la première moitié de liste ;
si l’élément milieu est inférieur dans l’ordre lexicographique au mot recherché, nous conservons la seconde moitié de liste.

Nous répétons l’opération en réduisant chaque fois la liste de moitié jusqu’à trouver l’élément recherché ou jusqu’à ce qu’il ne soit plus possible de réduire davantage la liste. Quand la liste ne peut plus être réduite, si l’élément n’a toujours pas été trouvé cela signifie qu’il ne figurait nulle part.

def recherche_dichotomique(terme, liste):

debut = 0

fin = len(liste) - 1

present = False

while debut <= fin and not present:

milieu = int(debut + (fin - debut) / 2)

if liste[milieu] == terme:

present = True

elif terme < liste[milieu]:

fin = milieu - 1

else:

debut = milieu + 1

return present

Nous testons le bon fonctionnement de notre algorithme.

print(recherche_dichotomique('souris', lexique))

# affiche True

print(recherche_dichotomique('stylet', lexique))

# affiche False

Pour visualiser de manière détaillée le fonctionnement de notre algorithme et le nombre de tours de boucle effectués, nous insérons dans notre code un compteur et un affichage des valeurs des différentes variables.

def recherche_dichotomique_compteur(terme, liste):

debut = 0

fin = len(liste) - 1

present = False

compteur = 0

while debut <= fin and not present:

compteur += 1

milieu = int(debut + (fin - debut) / 2)

print('Tour de boucle', compteur)

print('début :', debut)

print('fin :', fin)

print('milieu :', milieu)

if liste[milieu] == terme:

present = True

elif terme < liste[milieu]:

fin = milieu - 1

else:

debut = milieu + 1

return present

Nous relançons les mêmes requêtes que précédemment.

print(recherche_dichotomique_compteur('souris', lexique))

Produit l’affichage suivant :

Tour de boucle 1
début : 0
fin : 9
milieu : 4
Tour de boucle 2
début : 5
fin : 9
milieu : 7
Tour de boucle 3
début : 8
fin : 9

milieu : 8
True

Évaluons aussi le cas de la recherche infructueuse.

print(recherche_dichotomique_compteur('stylet', lexique))

Produit l’affichage suivant :

Tour de boucle 1
début : 0
fin : 9
milieu : 4
Tour de boucle 2
début : 5
fin : 9
milieu : 7
Tour de boucle 3
début : 8
fin : 9

milieu : 8
Tour de boucle 4
début : 9
fin : 9
milieu : 9
False

Nous observons que notre algorithme dichotomique est plus performant que nos précédents algorithmes systématique et séquentiel.
Sa complexité est $\text{O}(\text{log}(\text{n}))$ au lieu de $\text{O}(\text{n})$ (non démontré ici).

On peut constater sur cet exemple simple que la recherche dichotomique réduit très vite la taille des portions de liste, que la recherche soit ou non fructueuse.

Cette optimisation a été rendue possible parce que la liste est triée. Nous avons exploité une caractéristique particulière de notre problème qui nous a permis de prendre des « raccourcis » en nous évitant d’avoir à chercher dans des pans entiers de la liste.

Conclusion :

Les listes ou tableaux sont des structures de données fréquemment utilisées en programmation. Il est donc nécessaire de disposer d’algorithmes permettant d’effectuer des recherches d’éléments et d’extremums au sein de ces listes.

Ensuite, nous avons vu les algorithmes de tri par sélection et par insertion. Et la possibilité de trier ces listes avec des algorithmes spécialisés réduit d’autant le coût de ces recherches, comme celui de la recherche par dichotomie.

Cours : Algorithmes sur les tableaux

Parcours séquentiel de liste

Modalités de parcours

Recherche d’occurrence

Recherche de toutes les occurrences

Recherche d’extremums

Calcul de moyenne

Coût algorithmique

Tri par sélection

Principe du tri par sélection

Implémentation

Terminaison et complexité

Tri par insertion

Principe du tri par insertion

Implémentation

Terminaison et complexité

Algorithme de recherche par dichotomie