Chapitre 5 : Tableaux⚓︎

Partie A - Notion de tableau⚓︎

Définition d'un tableau en extension⚓︎

Un tableau permet de stocker en mémoire plusieurs valeurs dans une seule variable.

Une façon de définir un tableau est d'indiquer entre crochets les différentes valeurs, séparées par des virgules. On parle alors de définition en extension.

Par exemple, le tableau jours défini ci-dessous contient sept chaînes de caractères :

jours = ["lundi", "mardi", "mercredi", "jeudi", "vendredi", "samedi", "dimanche"]

Accès aux valeurs grâce à leur indice⚓︎

Chaque valeur contenue dans un tableau est indexée par un entier supérieur ou égal à 0. Dans la mémoire de la machine, les valeurs sont stockées consécutivement. Pour accéder à la valeur d'indice n d'un tableau tab, on utilise la notation tab[n].

Modification des valeurs grâce à leur indice⚓︎

Pour modifier la valeur d'indice n contenue dans le tableau tab, il suffit d'utiliser une affectation du type tab[n] = nouvelle_valeur.

Mais si on tente d'accéder ou de modifier, dans un tableau, une valeur située à un indice qui n'existe pas, alors une erreur se produit.

Par exemple, pour le tableau jours défini précédemment, les sept valeurs ont des indices compris entre 0 et 6. Si on essaie d'accéder à la valeur d'indice 7, une erreur se produit.

IndexError: list index out of range

Exercice 5-01 : Tableaux définis en extension

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Définition d'un tableau en compréhension⚓︎

Si on souhaite stocker dans un tableau les carrés des entiers compris entre 0 et 10, on peut définir le tableau en extension :

tab = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

On constate qu'une telle définition n'est pas pratique, voire impossible à mettre en œuvre si le nombre de valeurs dans le tableau est grand.

On utilise alors une autre façon de définir le tableau : la définition en compréhension, qui est basée sur la notion de boucle.

tab = [k*k for k in range(11)]

Il faut comprendre qu'on affecte à la variable tab un tableau contenant les valeurs de k*k (soit k au carré) pour tous les entiers k compris entre 0 et 10 (c'est-à-dire les valeurs entières auxquelles correspondent range(11)).

Il est également possible d'ajouter une condition à la définition en compréhension.

Par exemple, pour obtenir le carré des nombres pairs compris entre 0 et 10, on écrit :

tab = [k*k for k in range(11) if k % 2 == 0]

Pour définir, par exemple, un tableau qui contient 100 fois la valeur 0, on peut écrire :

tab = [0 for _ in range(100)]

ou alors, de façon encore plus simple, utiliser l'opérateur * :

tab = [0] * 100

Enfin, l'opérateur + permet de concaténer (c'est-à-dire mettre bout à bout) plusieurs tableaux. Par exemple, le tableau :

tab = [0]*5 + [1]*3 + [5*k for k in range(10) if k % 3 != 0]

est le tableau défini en compréhension qui correspond au tableau défini en extension :

tab = [0, 0, 0, 0, 0, 1, 1, 1, 5, 10, 20, 25, 35, 40]

Exercice 5-02 : Tableaux définis en compréhension

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Remarquons enfin qu'en théorie la taille d'un tableau est fixée et ne peut pas être modifiée. En Python, les tableaux sont en réalité des tableaux dynamiques pour lesquels il est possible d'ajouter ou de retirer des éléments. Nous verrons en Terminale que ce comportement est celui des listes et non des tableaux.

Pour ajouter un élément à la fin de tab, on utilise l'instruction tab.append(element).
Pour ajouter un élément à l'indice n dans tab, on utilise l'instruction tab.insert(n, element).
Pour supprimer l'élément d'indice n dans tab, on utilise l'instruction del tab[n].

Partie B - Tri d'un tableau : algorithmes de tri par sélection et de tri par insertion⚓︎

Objectif⚓︎

Le but de cette partie est d'étudier deux algorithmes permettant de trier les élements d'un tableau du plus petit au plus grand. Les éléments peuvent être des nombres mais aussi, par exemple, des chaînes de caractères (ou tout autre objet dont le type possède un ordre total, c'est-à-dire un ordre pour lequel tout élément peut être comparé à tout autre élément).

Tri par sélection⚓︎

Le principe du tri par sélection est le suivant :

On parcourt le tableau de la gauche vers la droite, en définissant une partie gauche déjà triée et une partie droite pas encore triée.
On détermine quel est le plus petit élément de la partie de droite, et on l'échange avec le premier élément de la partie de droite.

De cette façon, la partie de gauche du tableau est triée en permanence, et les éléments y sont placés à leur position définitive.

En vert, la partie gauche du tableau est triée. En rouge, la partie droite a tous ses éléments plus grands que les éléments de la partie gauche.

Algorithme de tri par sélection

Début

n ← longueur du tableau tab

Pour k allant de 0 à (n-2) faire

i ← indice du plus petit élement de tab dont l'indice est compris entre k et (n-1)

Echanger le kème élement et le ième élement du tableau tab

Fin Pour

Fin

Activité 5-03 : Tri par sélection

Objectif : Comprendre et implémenter l'algorithme de tri par sélection.

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Tri par insertion⚓︎

Le principe du tri par insertion est le suivant :

On parcourt le tableau de la gauche vers la droite, en définissant une partie gauche déjà triée et une partie droite pas encore triée.
On déplace le premier élément de la partie de droite au bon endroit dans la partie de gauche.

De cette façon, la partie de gauche du tableau est triée en permanence mais les éléments n'y sont pas placés à leur position définitive.

En vert, la partie gauche du tableau est triée. En rouge, le premier élément de la partie droite doit être inséré au bon endroit dans la partie gauche.

Algorithme de tri par insertion

Début

n ← longueur du tableau tab

Pour k allant de 1 à (n-1) faire

valeur ← tab[k]

pos ← k

Tant que pos > 0 et tab[pos - 1] > valeur faire

tab[pos] ← tab[pos - 1]

pos ← pos - 1

Fin Tant que

tab[pos] ← valeur

Fin Pour

Fin

Activité 5-04 : Tri par insertion

Objectif : Comprendre et implémenter l'algorithme de tri par insertion, puis comparer son efficacité avec celle de l'algorithme de tri par sélection.

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Partie C - Tableaux à plusieurs dimensions⚓︎

Nous avons vu jusqu'à présent des tableaux contenant des valeurs de type entier ou de type chaîne de caractères, mais les valeurs peuvent en réalité être de n'importe quel type.

En particulier, un tableau peut contenir des tableaux. On parle alors de tableau à deux dimensions.

Par exemple, le tableau union_europeenne défini ci-dessous est un tableau à deux dimensions contenant 27 tableaux qui correspondent à chaque état-membre de l'UE. On stocke en mémoire l'équivalent d'un tableau composé de 27 lignes et 2 colonnes.

union_europeenne = [
    ["Allemagne", "Berlin"], ["Belgique", "Bruxelles"], ["France", "Paris"],
    ["Luxembourg", "Luxembourg"], ["Italie", "Rome"], ["Pays-Bas", "Amsterdam"],
    ["Danemark", "Copenhague"], ["Irlande", "Dublin"], ["Grèce", "Athènes"],
    ["Espagne", "Madrid"], ["Portugal", "Lisbonne"], ["Autriche", "Vienne"],
    ["Finlande", "Helsinki"], ["Suède", "Stockholm"], ["Chypre", "Nicosie"],
    ["Estonie", "Tallinn"], ["Hongrie", "Budapest"], ["Lettonie", "Riga"],
    ["Lituanie", "Vilnius"], ["Malte", "La Valette"], ["Pologne", "Varsovie"],
    ["République Tchèque", "Prague"], ["Slovaquie", "Bratislava"], ["Slovénie", "Ljubljana"],
    ["Bulgarie", "Sofia"], ["Roumanie", "Bucarest"], ["Croatie", "Zagreb"]
]

L'élément du tableau union_européenne d'indice 2 est un tableau contenant des chaînes de caractères.

Il correspond à la troisième ligne de union_europeenne.

Dans un tableau à deux dimensions, on utilise une double indexation pour accéder aux éléments du tableau. Le premier indice correspond au numéro de ligne (ici l'indice du pays dans le tableau union_europeenne) et le second au numéro de colonne (ici 0 pour le nom du pays et 1 pour sa capitale).

Par exemple, l'instruction :

print(f"{union_europeenne[2][1]} est la capitale de {union_europeenne[2][0]}.")

affiche à l'écran la chaîne "Paris est la capitale de France."

Exercice 5-05 : Tableau à deux dimensions

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Partie D - Exercices et activités⚓︎

Exercices 5-06 et 5-07

Exercice 5-06 : Fonction mystèreExercice 5-07 : Tables d'addition et de multiplication

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Carnet Jupyter à télécharger ici

Corrigé disponible ici

Activités 5-08 et 5-09

Activité 5-08 : Fonctions et procédures avec des tableauxActivité 5-09 : Cases grises

Carnet Jupyter à télécharger ici

Carnet Jupyter accessible sur CAPYTALE

Corrigé disponible ici

Carnet Jupyter à télécharger ici

Corrigé disponible ici

Ce qu'il faut savoir et savoir faire⚓︎

Définir un tableau en extension.
Utiliser la fonction len pour déterminer le nombre d'éléments d'un tableau.
Accéder à, ou modifier, une valeur contenue dans un tableau, à partir de son indice.
Éviter les erreurs en se souvenant que les indices des éléments d'un tableau sont compris entre 0 et len(tableau)-1.
Définir un tableau en compréhension.
Utiliser les opérateurs * et + sur des tableaux.
Connaître l'algorithme de tri par sélection.
Connaître l'algorithme de tri par insertion.
Savoir que l'algorithme de tri par sélection a une complexité quadratique dans tous les cas.
Savoir que l'algorithme de tri par insertion a une complexité quadratique dans le pire des cas, et une complexité linéaire dans le meilleur des cas.
Mesurer le temps d'exécution d'une partie de programme grâce à la fonction time du module time.
Définir un tableau à deux dimensions.
Utiliser la double indexation des éléments d'un tableau à deux dimensions pour accéder aux élements d'un tel tableau.