Médaille
N°1 pour apprendre & réviser du collège au lycée.
Algorithmes sur les tableaux

Déjà plus de

1 million

d'inscrits !

Ce cours est en cours de création par nos équipes et il sera prêt pour la rentrée 2019 💪

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

bannière rappel

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.

bannière definition

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

bannière rappel

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.

bannière definition

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

bannière definition

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

bannière attention

Attention

Il n’est en revanche pas possible de calculer la moyenne d’une liste de chaines 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 nn d’éléments dans la liste, on parcourt au plus nn éléments.

bannière à retenir

À retenir

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

bannière astuce

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]

bannière astuce

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.

bannière à retenir

À retenir

Les boucles étant imbriquées le coût est quadratique. La complexité du tri par sélection est O(n2)\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]

bannière astuce

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.

bannière à retenir

À retenir

Le coût est quadratique, la complexité temporelle de l’algorithme de tri par insertion est O(n2)\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 O(nlogn)\text{O}(n\,\text{log}\,n).

bannière astuce

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, étudiée dans le cours « Terminaison et complexité », dont le coût est réduit mais qui requiert en entrée une liste ordonnée.

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.