Cours issu de : https://info.blaisepascal.fr/nsi-parcours-sequentiel-dun-tableau

et de : https://emilypython.wordpress.com/2018/11/06/listes-de-nombres-en-python-maximum-et-minimum/

Parcours séquentiel d’un tableau

Notion de tableau

Source : https://fr.wikipedia.org/wiki/Tableau_(structure_de_données)

En informatique, un tableau est une structure de données représentant une séquence finie d’éléments auxquels on peut accéder efficacement par leur position, ou indice, dans la séquence. C’est un type de conteneur que l’on retrouve dans un grand nombre de langages de programmation. On parle aussi de tableau indexé.

Dans les langages à typage statique (comme C, Java et OCaml), tous les éléments d’un tableau doivent être du même type. Certains langages à typage dynamique (tels que Python) permettent des tableaux hétérogènes.

Tableaux en Python

En Python, les tableaux sont représentés grâce à des objets de type list. Une liste ressemble à un p-uplet : un ensemble ordonné d’éléments avec des indices pour les repérer.

D’un point de vue syntaxique, les éléments d’une liste sont séparés par des virgules et entourés de crochets :

L = [45, 21, 56 ,12, 1, 8, 30, 22, 6, 33]

Mais on peut également considérer que les chaînes de caractères sont des conteneurs de caractères.

S = "Numérique et Sciences Informatiques !"

On accède aux éléments de ces tableaux grâce à leur propriété d’itérateurs, par leur indice.

>>> L[3] 

12 

>>> S[13] 

'S'

Tableaux en Javascript

Créer un tableau

var L = [45, 21, 56 ,12, 1, 8, 30, 22, 6, 33];

console.log(L[0]);         // accès par indice

console.log(L.length);     // longueur du tableau

Boucler sur un tableau

L.forEach(function(item, index, array) {

   console.log(item, index);

   });

Pour la suite, nous utiliserons Python, et travaillerons sur une liste de nombres entiers générés aléatoirement :

from random import randint

L = [randint(1, 100) for i in range(10)]

Parcours et Itération

En Python, les listes, les chaînes de caractères, les tuples, et un grand nombre d’autres objets sont des itérateurs : il contiennent dans leur structure les méthodes permettant de les parcourir.

Par indice

On peut parcourir un tableau en faisant évoluer un indice :

i = 0                 # initialisation de i

while i < len(L):     # vérification

   print(L[i])

   i += 1             # incrémentation de i

for i in range(len(L)):

    print(L[i])

Par valeur

Les listes Python possèdent leur propre propriété d’itération, on peut donc directement itérer sur les valeurs :

for e in L:

   print(e)

Par indice et valeur

Il est parfois intéressant d’avoir à la fois l’indice et la valeur d’un élément de la liste :

for i, e in enumerate(L):

   print(i, e)

Recherche d’une occurrence

Il s’agit de déterminer la position (l’indice) d’un élément e prétendument présent dans la liste L . On parle d’occurrence de e dans L .

Algorithme

Un « pointeur » i , initialisé à zéro, permet d’accéder aux éléments de la liste L . A chaque itération, on compare l’élément d’indice i de la liste avec l’élément e recherché. S’ils sont égaux, cela signifie que l’indice de e dans L vaut i et les itérations cessent, dans le cas contraire, on incrémente i et on fait une nouvelle itération. Si l’élément e n’est pas dans la liste L , le pointeur va jusqu’au bout de la liste, et finit par prendre la valeur de la longueur de la liste.

Implémentation en Python

def indice(e, L):

   i = 0

   continuer = True

   while i < len(L) or continuer:

      if L[i] == e:

         continuer = False

      else:

         i = i + 1

   return i 

Remarque : si i == len(L) alors cela signifie que L ne contient aucune occurrence de e .

Coût

Nous supposerons que chaque opération (affectation, comparaison, opération arithmétique, …) a un coût de 1 « unité » de temps.

Si n est la longueur de la liste L , on peut calculer la complexité ainsi :

def indice(e, L):

   i = 0                              # 1 (une affectation)

   continuer = True                   # 1 (une affectation)

                                      # dans le pire des cas, on itère n fois

   while i < len(L) and continuer:      # 3 (une comparaison, une interrogation de longueur de liste, une opération booléenne

      if L[i] == e:                     # 2 (une interrogation de liste, une affectation) 

         continuer = False              # 1 (une affectation)

      else:                           # Pire des cas = on continue !

         i = i + 1                      # 2 (une opération, une affectation)

   return i 

Complexité : T(n)=2+7×n=O(n)

Coût linéaire !

Méthode Python

L.index(e)

Renvoie l’indice de l’élément e dans la liste L.

Attention :

• si e n’est pas dans L , L.index(e) provoque une erreur !
• s’il y a plusieurs occurrences de e dans L , seul l’indice de la première est renvoyé.

Recherche des extremums

Algorithme

Pour connaitre la valeur maximale des valeurs contenues dans la liste L , il faut évaluer tour à tour tous les éléments e de L .

La valeur maximale à une étape donnée est mémorisée dans une variable m , initialisée avec le premier élément de la liste L .

Si l’élément e est supérieur à m , m prend alors la valeur de e.

Implémentation en Python

Maximum

La méthode pour trouver le maximum est la suivante : on crée une variable maxi à laquelle on affecte la valeur du premier élément de la liste. Puis on parcourt le tableau et on compare à chaque fois l’élément atteint avec maxi. Si l’élément est supérieur ou égal à maxi, on affecte cet élément à maxi.

La fonction Python suivante prend en paramètre une liste non vide de nombres et renvoie son maximum.

def maximum(liste):

    maxi = liste[0]

    for i in liste:

        if i >= maxi:

            maxi = i

    return maxi

On peut comparer avec > ou >=, cela ne change pas le résultat.

Ici, l’algorithme parcourt directement les éléments de la liste avec for i in liste, on peut directement travailler avec i.

La même fonction en parcourant les indices serait :

def maximumIndices(liste):

    maxi = liste[0]

    longueur=len(liste)

    for i in range(longueur):

        if liste[i] >= maxi:

            maxi = liste[i]

    return maxi

Emplacement du maximum

En parcourant les indices, on peut créer la fonction dernierIndiceMaximum qui, lorsqu’on lui passe en paramètre une liste non vide de nombres, renvoie l’indice du maximum :

def dernierIndiceMaximum(liste):

    maxi = liste[0]

    longueur=len(liste)

    indice_max = 0

    for i in range(longueur):

        if liste[i] >= maxi:

            maxi = liste[i]

            indice_max = i

    return indice_max

Ici la comparaison est importante : si le maximum apparait plusieurs fois, la fonction va renvoyer le plus grand des indices. Si on remplace >= par >, elle ne va plus renvoyer le plus grand, mais le plus petit des indices des maximums.

Minimum

Pour trouver le minimum ou son emplacement, il suffit de reprendre les fonctions déjà vues et de modifier la comparaison dans le test : on remplace >= par <= ou > par <.

Coût

La complexité de cet algorithme est en O(n).

Méthode Python

Il existe deux fonctions max() et min() permettant de déterminer les extrémums d’une liste.

Sources : cours sur la complexité algorithmique : https://www.supinfo.com/cours/2ADS/chapitres/01-notion-complexite-algorithmique