def tri_a_bulles(T):
  N = len(T)
  for k in range(N,1,-1):
    for i in range(0,k-1):
      if T[i] > T[i+1]:
        T[i],T[i+1] = T[i+1],T[i]
    

def tri_par_selection(T):
  N = len(T)
  for i in range(0,N-1):
    k = i
    for j in range(i+1,N):
      if T[j] < T[k]:
        k = j
    T[i],T[k] = T[k],T[i]
    

def partition(T,premier,dernier):
  pivot = dernier-1
  i = premier; j = pivot-1
      
  while True:
    while T[i] < T[pivot]:
      i += 1
    while j >= 0 and T[pivot] < T[j]:
      j -= 1
    if j < i:
      break
    T[i],T[j] = T[j],T[i]
      
  T[i],T[pivot] = T[pivot],T[i]
  return i
    

def tri_rapide_rec(T,premier,dernier):   # dernier non compris.
    if premier < dernier-1:              # >= 2 éléments
        pivot = dernier - 1              # choix du pivot
        T[pivot],T[dernier-1] = T[dernier-1],T[pivot]
        
        pivot = partition(T,premier,dernier)
        
        tri_rapide_rec(T,premier,pivot)
        tri_rapide_rec(T,pivot+1,dernier)


def tri_rapide(T):
    tri_rapide_rec(T,0,len(T))

def creer_tas(T):
    for i in range(parent(len(T)-1),-1,-1):
        descendre(T,i)
      
def descendre(T,i):
    e = plus_grand_enfant(T,i)
    while e < len(T) and T[i] < T[e]:
        T[i],T[e] = T[e],T[i]
        i = e
        e = plus_grand_enfant(T,i)
      
def plus_grand_enfant(T,i):
    pge, e2 = enfants(i)
    if e2 < len(T) and T[e2] > T[pge]:
        pge = e2
    return pge
      
def enfants(i):
    return 2*i+1, 2*i+2
  
def parent(i):
    return (i-1) // 2

def tri_par_tas(T):
    creer_tas(T)
    for i in range(len(T)-1,0,-1):
        T[i],T[0] = T[0],T[i]
        descendre(T,0,i)
        
def descendre(T,i,n):
    if n == None: n = len(T)
    e = plus_grand_enfant(T,i,n)
    while e < n and T[i] < T[e]:
        T[i],T[e] = T[e],T[i]
        i = e
        e = plus_grand_enfant(T,i,n)

def plus_grand_enfant(T,i,n):
    pge, e2 = enfants(i)
    if e2 < n and T[e2] > T[pge]:
        pge = e2
    return pge