É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 :

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 ! Observez sur cette photo comment se comporte le liquide ... (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.

C'est un échange simultané. Souvenez vous du tout premier exemple, où une variable en "écrasait" une autre ...

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 rien

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 inclus,
- É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(n - 1, 0, -1):
        j = randint(0, i)
        echange(tableau, i, j)