#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 21 17:06:13 2022

@author: leprince
"""

def pivot(l):
    n=len(l)
    p=l[0]
    LG=[]
    LD=[]
    for i in range(1,n):
        if l[i]<=p:
            LG.append(l[i])
        else :
            LD.append(l[i])
    return [p,LG,LD]

def triRapide(l):
    if len(l)<=1:
        return l
    else :
        A=pivot(l)
        return triRapide(A[1]) + [A[0]] + triRapide(A[2])
    
    
T = [4,9,7,0,1,2,5,3,6,8]

#print(triRapide(T))


def pivotage(T,g,d):
    pivot=T[g]
    i=g+1# indice du premier non traité
    indp=g#future place du pivot (dernier <= pivot dans partie traitée)
    while i<d:
        if T[i]<=pivot:
            T[indp+1],T[i]=T[i],T[indp+1]
            indp+=1
        i+=1    
    T[g],T[indp]=T[indp],T[g]        
    return indp    

def triRapideEnPlacePart(T,g,d):
    # cas de base : si d-g <= 1, on ne fait rien
    if d-g > 1:
        m = pivotage(T,g,d) #affecte à m l'indice du pivot 
                                  #et effectue le pivotage sur T
        triRapideEnPlacePart(T,g,m)
        triRapideEnPlacePart(T,m+1,d)
        

def triRapideEnPlace(T):
    triRapideEnPlacePart(T,0,len(T))

T = [4,9,7,0,1,2,5,3,6,8]
triRapideEnPlace(T)
print(T)