from random import *
T=[i for i in range (20)]
print(T)
shuffle(T)
print(T)

## partie 1 : selection
def echange(l,i,j):
    # echange 2 valeurs d'une liste
    l[i],l[j] = l[j], l[i]
 
# Q1.   
def tri_selection(l):
    for i in range(len(l)-1):
        mini=i
        for j in range(i+1,len(l)):
            if l[j]<l[mini]: 
                mini=j
        echange(l,i,mini)
        # print(l) # pour voir tourner
    return l

#test
T=tri_selection(T)
print("la liste est triee", T)

# Q2. complexité : 0(n²) dans tous les cas avec les 2 boucles imbriqués (somme (n-i) comparaisons, chgt de variable -> n(n-1)/2 comparaisons)
#Ce n’est donc pas un tri très efficace, mais en revanche c’est un tri très simple à comprendre !


# Q3. danse
def tri_selection2(l): # evite la variable mini
    for i in range(len(l)-1):
        for j in range(i+1,len(l)):
            if l[j]<l[i]: 
                echange(l,j,i)
    return l
#test
shuffle(T)
print(tri_selection2(T))

## partie 2 : insertion
# Q4.
def tri_insertion(L):
    for i in range(1,len(L)):
        x=L[i]
        j=i
        while j>0 and L[j-1]>x:
            L[j]=L[j-1]
            j=j-1
            print(L) # pour voir tourner
        L[j]=x
    return L    

# test
shuffle(T)
print(tri_insertion(T))

# autre versin depuis le début de la liste
def tri_insertion2(L):
    for i in range(1,len(L)):
        x=L[i]
        j=0
        while j<=i-1 and L[j]<x:
            j=j+1
        for k in range(i-1, j-1,-1):#on echange les positions
            L[k+1]=L[k]
        L[j]=x
    return L


## partie 3 : fusion
# la fusion avec des files et la fonction pop
def fusion_IT(T,g,d,m):
    G=T[g:m+1]
    D=T[m+1:d+1]
    for k in range(g,d+1): #on replace dans T avec le bon ordre
        if len(G)>0 and len(D)>0 :
            if G[0]<=D[0]:
                T[k]=G.pop(0)
            else:
                T[k]=D.pop(0)
        elif len(G)==0 and len(D)>0: T[k]=D.pop(0)
        elif len(D)==0 and len(G)>0 : T[k]=G.pop(0)
    
# Q9
def Tri_fusion(T,g,d):
    if g<d:
        m=(g+d)//2
        Tri_fusion(T,g,m)
        Tri_fusion(T,m+1,d)
        fusion_IT(T,g,d,m)
    return T 
    
# test
shuffle(T)
print(Tri_fusion(T,0,len(T)-1))

# Q11        
def fusion(L1,L2):#Fusion de deux listes triées, méthode récursive
    if len(L1)==0:
        return L2
    if len(L2)==0:
        return L1
    if L1[0]>L2[0]:
        return [L2[0]]+fusion(L1,L2[1:])
    else:
        return [L1[0]]+fusion(L1[1:],L2)
# Q12
def tri_fusion(L):#Tri fusion
    if len(L)==1:
        return L
    else:
        print(L) # pour voir tourner
        return fusion(tri_fusion(L[:len(L)//2]),tri_fusion(L[len(L)//2:]))
# test
shuffle(T)
print(tri_fusion(T))
       
## partie 4 : rapide
# Q15
def tri_rapide(L) :
    if L == [] :
        return [] #Le tri rapide d'une liste vide renvoi une liste vide
    pivot = L[0]
    listebasse=[]
    listehaute=[]
    for i in range (1,len (L)) :
        if L[i] < pivot :
            listebasse.append(L[i])
        else :
            listehaute.append(L[i])
    print(listebasse,'    ',listehaute) #pour voir tourner
    return (tri_rapide(listebasse) + [pivot] + tri_rapide(listehaute))  

# test
shuffle(T)
print(tri_rapide(T))
  
# Q19
def segmente(T,i,j):
    g=i+1
    d=j
    p=T[i]
    while g<=d :
        while d>=i and T[d]>p:
            d=d-1
        while g<=j and T[g]<=p:
            g=g+1
        if g<d:
            echange(T,g,d)
            d=d-1
            g=g+1
    echange(T,i,d)
    return d
    
def Tri_rapide2(L, i, j):
    if i<j:
        k=segmente(L,i,j)
        Tri_rapide(L,i,k-1)
        Tri_rapide(L,k+1,j)
    return L

#test
shuffle(T)
print(Tri_rapide2(T, 0, len(T)-1))

## partie 5 : par comptage
# Q20
def tri_comptage(T,borneSup):
    # Création du tableau de comptage
    tabComptage=[0]*(borneSup+1)
    for i in range(len(T)):
        tabComptage[T[i]]+=1
    
    print("tabComptage",tabComptage) #pour voir tourner

    # Création du tableau trié
    x = 0
    for i in range(borneSup+1):
        for j in range(tabComptage[i]):
            T[x] = i
            x+=1
        print(T)#pour voir tourner
            
    return T
  
# test
T=[2,3,4,4,5,0,1,2,3,6,5,4,1,8,9,9,7,8,8,4,6,4,5,2,3,4]
print(tri_comptage(T,9))

## on pourrait utiliser module time pour mesurer le temps des algorithmes ...