Tri d'une pile

D'après 2022, Polynésie, J1, Ex. 4

La classe Pile utilisée dans cet exercice est implémentée en utilisant des listes Python et propose quatre éléments d'interface :

  • Un constructeur qui permet de créer une pile vide, représentée par [] ;
  • La méthode est_vide() qui renvoie True si l'objet est une pile ne contenant aucun élément, et False sinon ;
  • La méthode empiler qui prend un objet quelconque en paramètre et ajoute cet objet au sommet de la pile. Dans la représentation de la pile dans la console, cet objet apparait à droite des autres éléments de la pile ;
  • La méthode depiler qui renvoie l'objet présent au sommet de la pile et le retire de la pile.

Exemples :

🐍 Console Python
>>> ma_pile = Pile()
>>> ma_pile.empiler(2)
>>> ma_pile
[2]
>>> ma_pile.empiler(3)
>>> ma_pile.empiler(50)
>>> ma_pile
[2, 3, 50]
>>> ma_pile.depiler()
50
>>> ma_pile
[2, 3]

La méthode est_triee ci-dessous renvoie True si, en dépilant tous les éléments, ils sont traités dans l'ordre croissant, et False sinon.

🐍 Script Python
1
2
3
4
5
6
7
8
9
def est_triee(self):
    if not self.est_vide():
        e1 = self.depiler()
        while not self.est_vide():
            e2 = self.depiler()
            if e1 ... e2 :
                return False
            e1 = ...
    return True

1. Recopier sur la copie les lignes 6 et 8 en complétant les points de suspension.

Réponse
🐍 Script Python
1
2
3
4
5
6
7
8
9
def est_triee(self):
    if not self.est_vide():
        e1 = self.depiler()
        while not self.est_vide():
            e2 = self.depiler()
            if e1 > e2 :
                return False
            e1 = e2
    return True

On crée dans la console la pile A représentée par [1, 2, 3, 4].

2.a. Donner la valeur renvoyée par l'appel A.est_triee().

Réponse

La valeur \(4\) est d'abord dépilée, puis \(3\). L'ordre n'est pas croissant, ainsi A.est_triee() renvoie False.

2.b. Donner le contenu de la pile A après l'exécution de cette instruction.

Réponse

A sera représenté par [1, 2].

On souhaite maintenant écrire le code d'une méthode depile_max d'une pile non vide ne contenant que des nombres entiers et renvoyant le plus grand élément de cette pile en le retirant de la pile.

Après l'exécution de p.depile_max(), le nombre d'éléments de la pile p diminue donc de 1.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def depile_max(self):
    assert not self.est_vide(), "Pile vide"
    q = Pile()
    maxi = self.depiler()
    while not self.est_vide():
        elt = self.depiler()
        if maxi < elt:
            q.empiler(maxi)
            maxi = ...
        else :
            ...
    while not q.est_vide():
        self.empiler(q.depiler())
    return maxi

3. Recopier sur la copie les lignes 9 et 11 en complétant les points de suspension.

Réponse
🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def depile_max(self):
    assert not self.est_vide(), "Pile vide"
    q = Pile()
    maxi = self.depiler()
    while not self.est_vide():
        elt = self.depiler()
        if maxi < elt:
            q.empiler(maxi)
            maxi = elt
        else :
            q.empiler(elt)
    while not q.est_vide():
        self.empiler(q.depiler())
    return maxi

On crée la pile B représentée par [9, -7, 8, 12, 4] et on effectue l'appel B.depile_max().

4.a. Donner le contenu des piles B et q à la fin de chaque itération de la boucle while de la ligne 5.

Réponse
  • B contient [9, -7, 8, 12] ;
  • q est vide ;
  • maxi est égal à 4.

Juste avant le premier tour de boucle

  • B contient [9, -7, 8] ;
  • q contient [4] ;
  • maxi est égal à 12.
  • B contient [9, -7] ;
  • q contient [4, 8] ;
  • maxi est égal à 12.
  • B contient [9] ;
  • q contient [4, 8, -7] ;
  • maxi est égal à 12.
  • B est vide ;
  • q contient [4, 8, -7, 9] ;
  • maxi est égal à 12.

4.b. Donner le contenu des piles B et q avant l'exécution de la ligne 14.

Réponse

La dernière boucle renverse la pile q dans la pile B, ainsi, à la ligne 14 :

  • q est vide ;
  • B contient [9, -7, 8, 4].

4.c. Donner un exemple de pile qui montre que l'ordre des éléments restants n'est pas préservé après l'exécution de depile_max.

Réponse

Avec une pile B qui contient [3, 1, 2]

  • B contient [3, 1] ;
  • q est vide ;
  • maxi est égal à 2.

Juste avant le premier tour de boucle

  • B contient [3] ;
  • q contient [1] ;
  • maxi est égal à 2.
  • B est vide ;
  • q contient [1, 2] ;
  • maxi est égal à 3.

La dernière boucle renverse la pile q dans la pile B, ainsi, à la ligne 14 :

  • q est vide ;
  • B contient [2, 1].

Sans 3 dans la pile B initiale, on a dans l'ordre [1, 2] ce qui est différent de [2, 1] obtenu ici avec depile_max.

On a ainsi un exemple où l'ordre des éléments restants n'est pas préservé après l'exécution de depile_max.

On donne le code de la fonction traiter :

🐍 Script Python
1
2
3
4
5
6
def traiter(self):
    q = Pile()
    while not self.est_vide():
        q.empiler(self.depile_max())
    while not q.est_vide():
        self.empiler(q.depiler())

5.a. Donner les contenus successifs des piles B et q

  • avant la ligne 3,
  • avant la ligne 5,
  • à la fin de l'exécution de la fonction traiter lorsque la fonction traiter est appelée avec la pile B contenant [1, 6, 4, 3, 7, 2].
Réponse

Avec B = [1, 6, 4, 3, 7, 2], un appel B.traiter() conduit successivement à :

  • Avant la ligne 3,
    • B contient [1, 6, 4, 3, 7, 2] ;
    • q est vide.
  • Avant la ligne 5,
    • B est vide ;
    • q contient [7, 6, 4, 3, 2, 1]
  • À la fin,
    • B contient [1, 2, 3, 4, 6, 7]
    • q est vide.

5.b. Expliquer le traitement effectué par cette méthode.

Réponse

Ce traitement est un tri de la pile. On construit d'abord q comme la pile des éléments de self dans l'ordre décroissant. On renverse ensuite la pile, qui se retrouve comme si on avait empilé les éléments de self dans l'ordre croissant.

Attention, il s'agit de l'ordre inverse de celui proposé par la fonction est_triee vu à la question 1. ici, si on dépile les éléments, ils sont désormais dans l'ordre décroissant.