"""
░▒▓████████▓▒░▒▓███████▓▒░          ░▒▓█▓▒░  ░▒▓█▓▒░
   ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░      ░▒▓████▓▒░▒▓████▓▒░
   ░▒▓█▓▒░   ░▒▓█▓▒░░▒▓█▓▒░         ░▒▓█▓▒░  ░▒▓█▓▒░
   ░▒▓█▓▒░   ░▒▓███████▓▒░          ░▒▓█▓▒░  ░▒▓█▓▒░
   ░▒▓█▓▒░   ░▒▓█▓▒░                ░▒▓█▓▒░  ░▒▓█▓▒░
   ░▒▓█▓▒░   ░▒▓█▓▒░                ░▒▓█▓▒░  ░▒▓█▓▒░
   ░▒▓█▓▒░   ░▒▓█▓▒░                ░▒▓█▓▒░  ░▒▓█▓▒░

___________      .__                       .__    .___
\__    ___/______|__| ____________  ______ |__| __| _/____
  |    |  \_  __ \  | \_  __ \__  \ \____ \|  |/ __ |/ __ \
  |    |   |  | \/  |  |  | \// __ \|  |_> >  / /_/ \  ___/
  |____|   |__|  |__|  |__|  (____  /   __/|__\____ |\___  >
                                  \/|__|           \/    \/
"""
CGRAS   = '\033[1m'
CEND   = '\x1b[0m'
CGREEN = "\x1b[36m"
CRED   = "\x1b[35m"


## Tri rapide

listeP1 = [13,12,4,12,17,49,21,33,22,17,21,1,23,49, 1]
listeP2 = [13,2,14,29,17,43,21,33,22,42,55,5,27,49,23]

def partition(L:list, a:int, b:int):
    iPivot = a



    return iPivot


print(CGREEN+"1.a.- Avant partitionnement :"+CEND)
print("listeP2 =",listeP2)


print(CGREEN+"1.b.- Après partitionnement :"+CEND)
pos1 = partition(listeP2,0,len(listeP2)-1);
print(CRED+"Pivot = "+str(listeP2[pos1])+" en position "+str(pos1)+CEND)
print("listeP2 =",listeP2)

print(CGREEN+"1.c.- Partitionnement de la 1ère moitié: "+str(listeP2[0:pos1])+CEND)
pos2 = partition(listeP2,0,pos1-1);
print(CRED+"Pivot =  "+str(listeP2[pos2])+" en position "+str(pos2)+CEND)
print("listeP2 =",listeP2)

print(CGREEN+"1.c.- Partitionnement de la 2nde moitié: "+str(listeP2[pos1+1:])+CEND)
pos3 = partition(listeP2,pos1+1,len(listeP2)-1);
print(CRED+"Pivot = "+str(listeP2[pos3])+" en position "+str(pos3)+CEND)
print("listeP2 =",listeP2)


## Tri rapide : un exemple de la stratégie "diviser pour régner"

def triRapide(L: list, a:int, b:int):
    """
    Tri de la liste L d'entiers entre les éléments d'indice a et b
    """
    if b>a:
        iPivot = 0



    # sinon : un seul élément (a=b) entre l'indice a et l'indice b
    # ou zéro élément (a>b) entre l'indice a et l'indice b ....
    # ... ce dernier cas peut advenir lorsque iPivot=a
    return None

# Tests
"""
print(CGREEN+CGRAS+"\n2.a.- Tri rapide -- Essai n°1"+CEND)
listeP2 = [13,2,14,29,17,43,21,33,22,42,55,5,27,49,23]
print(CGRAS+"Essai de triRapide sur \nlisteP2="+str(listeP2)+CEND)
n = len(listeP2)
triRapide(listeP2,0,n-1)
print(CRED+CGRAS+"Résultat:"+CEND)
print(CGRAS+"listeP2="+str(listeP2)+CEND)

print(CGREEN+CGRAS+"\n2.b.- Tri rapide -- Essai n°2"+CEND)
listeP1 = [13,12,4,12,17,49,21,33,22,17,21,1,23,49, 1]
print(CGRAS+"Essai de triRapide sur \nlisteP1="+str(listeP1)+CEND)
n = len(listeP1)
triRapide(listeP1,0,n-1)
print(CRED+CGRAS+"Résultat:"+CEND)
print(CGRAS+"listeP1="+str(listeP1)+CEND)
"""
"""
________ _________________________   ______                  _____
___  __ \__  ____/__  ___/____  _/   __|__ \   _______ _____ __  /_
__  /_/ /_  /     _____ \  __  /     ____/ /   __  __ \_  _ \_  __/
_  ____/ / /___   ____/ / __/ /      _  __/___ _  / / //  __// /_
/_/      \____/   /____/  /___/      /____/_(_)/_/ /_/ \___/ \__/


"""