Échanger des éléments⚓︎

Problème et solution⚓︎

Lors du tri de tableaux, nous allons bien souvent échanger des valeurs.

Par exemple, échanger "Riri" et "Loulou" dans le tableau ci-dessous :

🐍 Script Python

neveux = ["Riri", "Fifi", "Loulou"]
neveux[0] = neveux[2]
neveux[2] = neveux[0]

Question

Quelle est la valeur de neveux après l'exécution des ces instructions ?

Cocher l'affirmation correcteSolution

["Riri", "Fifi", "Loulou"]
["Loulou", "Fifi", "Loulou"]
["Loulou", "Fifi", "Riri"]
["Riri", "Fifi", "Riri"]

["Riri", "Fifi", "Loulou"]
["Loulou", "Fifi", "Loulou"]
["Loulou", "Fifi", "Riri"]
["Riri", "Fifi", "Riri"]

En effet, l'instruction neveux[0] = neveux[2] affecte la valeur "Loulou" à la cellule d'indice 0. Le "Riri" est donc « écrasé ». L'instruction neveux[2] = neveux[0] ne fait alors que recopier le "Loulou" dans la cellule d'indice 2.

Nous ne pouvons donc pas procéder ainsi. À moins de pouvoir effectuer les deux instructions « en même temps » (nous verrons cela un peu plus loin).

Si l'on se représente le problème différemment, échanger les valeurs dans un tableau s'apparente à échanger le contenu des deux verres ci-dessous.

Deux verres

Comme on peut l'imaginer, il est nécessaire d'utiliser un troisième verre : nous devons utiliser une troisième variable.

Question

Compléter le script ci-dessous permettant d'échanger les valeurs d'indices 0 et 1 de la list fruits.

###

Solution

On utilise une variable temporaire pour stocker la valeur de fruits[1].

🐍 Script Python

fruits = ['Poire', 'Pomme']

temporaire = fruits[1]
fruits[1] = fruits[0]
fruits[0] = temporaire

On pourrait aussi affecter fruits[0] à temporaire :

🐍 Script Python

temporaire = fruits[0]
fruits[0] = fruits[1]
fruits[1] = temporaire

Dans une fonction⚓︎

Nous allons faire un usage intensif des échanges de valeurs. Regroupons ce code dans une fonction.

Question : la fonction echange

Compléter la fonction echange qui prend en argument un tableau ainsi que deux entiers i et j et échange les éléments d'indices i et j dans tableau.

On garantit que i et j sont des indices valides.

Attention

Cette fonction ne renvoie rien !

###

Solution

🐍 Script Python

def echange(tableau, i, j):
    temporaire = tableau[j]
    tableau[j] = tableau[i]
    tableau[i] = temporaire

Attardons-nous sur ce code et observons son fonctionnement :

Comme on peut l'observer, le tableau fruits passé en paramètre à la fonction est directement modifiée par la fonction, quand bien même la variable utilisée dans la fonction est différente ; il s'agit de tableau.

Cette propriété est due au fait que lorsque Python transmet un tableau comme paramètre à une fonction, il transmet la référence du tableau et non sa valeur. Ainsi, le tableau modifié dans la fonction est le même que celui passé en paramètre.

Complément

Cette particularité des tableaux ne s'applique pas à tous les types de variables. Observez le script ci-dessous :

🐍 Script Python

def double(x):
    x = 2 * x

a = 8
double(a)

À l'issue de ce code a vaut toujours 8. En effet dans le cas des entiers, Python passe la valeur de l'entier en paramètre, pas sa référence.

Les tableaux (et les list) Python ont une autre particularité importante : ce sont des objets mutables. Observez le fonctionnement du script ci-dessous :

Comme on peut le voir, lors de sa création, copie pointe vers la même valeur que fruits.

On modifie ensuite la copie, certes, mais comme les deux variables pointent vers la même list, l'original a aussi été modifié.

Ce mécanisme est très important et il faudra le garder à l'esprit.

En même temps !⚓︎

Revenons au cas des deux verres observés plus haut. Afin d'échanger leur contenu, il nous a semblé indispensable d'utiliser un troisième verre... Sauf si l'on est dans la station spatiale internationale ! (source : Nasa)

Liquide dans l'ISS

Python autorise ce genre d'astuce. Il est ainsi possible d'échanger deux valeurs « en même temps ».

Pour ce faire, on utilise l'affectation multiple :

🐍 Script Python

nombres = [0, 1, 6, 3, 4, 5, 2]
nombres[2], nombres[6] = nombres[6], nombres[2]

Notez comme l'ordre des indices a été échangé : 2 et 6 avant l'affectation, 6 et 2 après.

Nous pouvons désormais alléger la fonction echange.

Question : la fonction echange_V2

Modifier la fonction echange afin qu'elle utilise l'affectation multiple.

La modification du tableau se fera en place : la fonction ne renverra donc pas le tableau modifié.

###

Solution

🐍 Script Python

def echange(tableau, i, j):
    tableau[i], tableau[j] = tableau[j], tableau[i]

Question : la fonction renverse

On souhaite écrire une fonction renverse prenant en argument un tableau et le renversant : le premier élément est échangé avec le dernier, le deuxième avec l'avant-dernier etc, s'ils existent.

La modification s'effectuant en place, la fonction ne renverra rien.

###

Astuce

On doit échanger le premier élément et le dernier, le deuxième et l'avant-dernier, le troisième et l'avant-avant-dernier, etc. jusqu'à un certain point !

Solution

Il s'agit d'échanger les éléments du début du tableau avec ceux de la fin. On utilise deux indices i et j, l'un progressant du début vers la fin du tableau, l'autre de la fin vers le début.

À chaque étape du parcours, on échange les éléments d'indices i et j.

Lorsque i devient supérieur ou égal à j, cela signifie que l'on a dépassé le milieu du tableau : tous les échanges souhaités ont eu lieu.

🐍 Script Python

def renverse(tableau):
    i = 0
    j = len(tableau) - 1
    while i < j:
        echange(tableau, i, j)
        i += 1
        j -= 1

Question : la fonction melange

Avant de trier des tableaux, apprenons à les mélanger !

L'algorithme de Fisher-Yates est un classique et permet de mélanger un tableau en place.

Son fonctionnement est le suivant (on considère un tableau de longueur n) :

Effectuer un parcours à rebours des indices du tableau à l'aide d'une variable i allant de n - 1 inclus jusqu'à 0 exclu,
- À chaque itération, créer une variable j et lui affecter un entier aléatoire entre 0 inclus et i exclu,
- Échanger les éléments d'indice i et j dans le tableau,
- passer à l'itération suivante.

Compléter la fonction melange faisant subir cet algorithme à l'argument tableau.

###

Astuce (1)

La méthode randint du module random prend deux arguments a et b et renvoie un entier aléatoire entre a et b (inclus l'un et l'autre).

Astuce (2)

Pour effectuer le parcours à rebours allant de n - 1 inclus jusqu'à 0 exclu on peut saisir for i in range(n - 1, 0, -1):.

Solution

🐍 Script Python

def melange(tableau):
    for i in range(len(tableau) - 1, 0, -1):
        j = randint(0, i)
        echange(tableau, i, j)