Tri avec une pile

Une pile (en anglais stack) est une manière d'organiser des données, fondée sur le principe « dernier arrivé, premier sorti » (ou LIFO pour Last In, First Out), ce qui veut dire que les derniers éléments ajoutés à la pile seront les premiers à être récupérés.

Expliquation préalable

Comme vous le savez l'avantage de la pile par rapport à la liste est la faible complexité de ses primitives empiler et dépiler. Nous allons donc nous pencher sur la possibilité de réaliser un tri grâce à une pile.
Malheureusement, toutes les listes ne sont pas triables avec une seule pile.

Chaîne à afficher si l'image ne peut s'afficher — Si on note D et E les opérations d'empilage et de dépilage, la
liste [4, 1, 3, 2] peut être triée par la séquence EEDEEDDD.

Tests afin de comprendre

	     (2,4,1,3) ne peux pas être trié			  	   (3,1,2,5,4) peux être trié		     	            (4,5,3,7,2,1,6) ne peux pas être trié

Le code

from pile import PileOptim
def tri_en_pile(seq): 
    longueur = len(seq)
    p = PileOptim()
    indice_seq = 0 #indice du premier élément de la séquence non encore entré dans la pile
    pile_last = 0 #dernier des éléments à être sorti de la pile
    tri = []
    for i in range(2*longueur):
        if not p.est_vide(): #recupere la valeur de l'element au sommet de la pile
            x = p.depiler()
            p.empiler(x)
        else :
            x = None
        if not p.est_vide() and x == pile_last + 1: #si la liste n'est pas vide et que x suit l'enchainement du tri, on le dépile 
            pile_last = p.depiler()
        elif indice_seq < longueur: 
            p.empiler(seq[indice_seq])
            indice_seq += 1
        else:
            return False

        if tri==[]:
            if pile_last!=0:
                tri.append(pile_last)
        elif pile_last!=tri[len(tri)-1]:
            tri.append(pile_last)
    return tri
    
###________________________TEST________________________###
from random import randint,shuffle

valeurs=[]
for x in range(10):
    if valeurs==[]:
        valeurs=[1]
    else:
        valeurs.append(valeurs[len(valeurs)-1]+1)
    t1=[]
    compteur_true=0
    compteur_false=0
    for x in range (100000):
        valeur=valeurs[:]
        shuffle(valeur)
        t1.append(valeur)
    for val in t1:
        res = tri_en_pile(val)
        if res!=False:
            compteur_true+=1
        else :
            compteur_false+=1
    print(compteur_true, ":", compteur_false, "    pour", len(valeurs)," valeurs")