#### TP n°10: Tris ####
#################



### TRI PAR SÉLECTION ###
## Question 1 
def index_minimum(L:list) -> int:
    """ renvoie l'index du plus petit terme de la liste """
    imin=0
    for i in range(len(L)):
        if L[i]<L[imin]:
            imin=i
    return imin
## Test de la fonction `index_minimum`; **à exécuter sans éditer**
ok=True
if index_minimum([1,4,3,-1,3,6,2])!=3: ok=False
if index_minimum([1,4,3,-1,3,6,-2])!=6: ok=False
if index_minimum([-1,-4,-3])!=1: ok=False
if index_minimum([-5,-4,-3])!=0: ok=False
if ok:
    print("Fonction index_minimum: test réussi!")
else:
    print("Fonction index_minimum: test échoué!")

## Question 2 
def tri_par_selection(L:list) -> list:
    """ renvoie une copie triée de la liste """
    Ltri=[]
    while len(L)>0:
        imin=index_minimum(L)
        Ltri.append(L.pop(imin))
    return Ltri
## Test de la fonction `tri_par_selection`; **à exécuter sans éditer**
ok=True
if tri_par_selection([1,4,3,-1,1,2,3])!=[-1,1,1,2,3,3,4]: ok=False
if tri_par_selection([1,1,1,-1])!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_par_selection: test réussi!")
else:
    print("Fonction tri_par_selection: test échoué!")


### TRI PAR INSERTION ###
## Question 3 
def place_element(L : list, element):
    """ insère element à sa place dans la liste """
    if len(L)==0: 
        L.append(element) # ajout de l'élément à la fin
    elif element<=L[0]:
        L.insert(0,element) # ajout de l'élément avant le terme numéro 0
    elif element>L[len(L)-1]:
        L.append(element) # ajout de l'élément à la fin
    else:
        for i in range(len(L)):
            if L[i]< element and element <=L[i+1]:
                L.insert(i+1,element) # ajout de l'élément avant le terme i+1
L=[1,2,5,6,8,10,14,15]
print(L)
place_element(L,9)
print(L)

## Question 4 
def tri_par_insertion(L:list) -> list:
    Ltri=[]
    while len(L)>0:
        place_element(Ltri,L.pop())
    return Ltri
## Test de la fonction `tri_par_insertion`; **à exécuter sans éditer**
ok=True
if tri_par_insertion([1,4,3,-1,1,2,3])!=[-1,1,1,2,3,3,4]: ok=False
if tri_par_insertion([1,1,1,-1])!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_par_insertion: test réussi!")
else:
    print("Fonction tri_par_insertion: test échoué!")
## Question 5 
def place_element_dicho(L : list, element):
    """ insère element à sa place dans la liste """
    a,b=0,len(L)
    if b==0:
        L.append(element)
    elif element<L[a]:
        L.insert(0,element)
    elif element>L[b-1]:
        L.append(element)
    else:
        while b-a> 1:
            m=(a+b)//2
            if element> L[m]:
                a=m
            else:
                b=m
        L.insert(b,element)

def tri_par_insertion_dicho(L:list) -> list:
    Ltri=[]
    while len(L)>0:
        place_element_dicho(Ltri,L.pop())
    return Ltri
## Test de la fonction `tri_par_insertion_dicho`; **à exécuter sans éditer**
ok=True
if tri_par_insertion_dicho([1,4,3,-1,1,2,3])!=[-1,1,1,2,3,3,4]: ok=False
if tri_par_insertion_dicho([1,1,1,-1])!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_par_insertion_dicho: test réussi!")
else:
    print("Fonction tri_par_insertion_dicho: test échoué!")


### TRI À BULLES ###

## Question 6 
def tri_a_bulles(L:list) -> list:
    modification=True
    n=len(L)
    while modification==True:
        modification=False
        for i in range(n-1):
            if L[i+1]<L[i]:
                temp=L[i]
                L[i]=L[i+1]
                L[i+1]=temp
                modification=True
    return L
## Test de la fonction `tri_a_bulles`; **à exécuter sans éditer**
ok=True
if tri_a_bulles([1,4,3,-1,1,2,3])!=[-1,1,1,2,3,3,4]: ok=False
if tri_a_bulles([1,1,1,-1])!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_a_bulles: test réussi!")
else:
    print("Fonction tri_a_bulles: test échoué!")
## Question 7 
import numpy as np
import time
liste_n=[]
liste_temps_tri_a_bulles=[]
for n in range(1,4002,400):
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_a_bulles(liste)
    fin=time.time()
    liste_n.append(n)
    liste_temps_tri_a_bulles.append(fin-debut)
import matplotlib.pyplot as plt
plt.figure()
plt.plot(liste_n,liste_temps_tri_a_bulles)
plt.show()
### TRI À PEIGNE ###

## Question 8 
def tri_a_peigne(L:list) -> list:
    modification=True
    n=len(L)
    intervalle=len(L)
    while intervalle>1 or modification==True:
        intervalle=int((intervalle+0.3)/1.3)
        modification=False
        for i in range(n-intervalle):
            if L[i+intervalle]<L[i]:
                temp=L[i]
                L[i]=L[i+intervalle]
                L[i+intervalle]=temp
                modification=True
    return L
## Test de la fonction `tri_a_peigne`; **à exécuter sans éditer**
ok=True
if tri_a_peigne([1,4,3,-1,1,2,3])!=[-1,1,1,2,3,3,4]: ok=False
if tri_a_peigne([1,1,1,-1])!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_a_peigne: test réussi!")
else:
    print("Fonction tri_a_peigne: test échoué!")
## Question 9 
import numpy as np
import time
liste_n=[]
liste_temps_tri_a_peigne=[]
for n in range(1,100002,10000):
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_a_peigne(liste)
    fin=time.time()
    liste_n.append(n)
    liste_temps_tri_a_peigne.append(fin-debut)
import matplotlib.pyplot as plt
plt.figure()
plt.plot(liste_n,liste_temps_tri_a_peigne)
plt.show()
### TRI PAR FUSION ###

## Question 10 
def tri_fusion(L:list) -> list:
    if len(L)<=1:
        return L
    i1,i2=0,0
    L_triee=[]
    m=len(L)//2
    l1,l2=tri_fusion(L[:m]),tri_fusion(L[m:])
    while i1<len(l1) or i2<len(l2):
        if i1>=len(l1):
            L_triee.append(l2[i2])
            i2=i2+1
        elif i2>=len(l2):
            L_triee.append(l1[i1])
            i1=i1+1
        else:
            if l1[i1]<l2[i2]:
                L_triee.append(l1[i1])
                i1=i1+1
            else:
                L_triee.append(l2[i2])
                i2=i2+1
    return L_triee
## Test de la fonction `tri_fusion`; **à exécuter sans éditer**
ok=True
if tri_fusion([1,4,3,-1,1,2,3])!=[-1,1,1,2,3,3,4]: ok=False
if tri_fusion([1,1,1,-1])!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_fusion: test réussi!")
else:
    print("Fonction tri_fusion: test échoué!")
## Question 11 
import numpy as np
import time
liste_n=[]
liste_temps_tri_fusion=[]
for n in range(1,100002,10000):
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_fusion(liste)
    fin=time.time()
    liste_n.append(n)
    liste_temps_tri_fusion.append(fin-debut)
import matplotlib.pyplot as plt
plt.figure()
plt.plot(liste_n,liste_temps_tri_fusion)
plt.show()
### TRI RAPIDE ###

## Question 12 
def echange(L:list,i:int,j:int):
    # cette fonction échange les cases i et j de la liste L
    temp=L[i]
    L[i]=L[j]
    L[j]=temp
## Question 13 
def partitionne(L:list,premier:int,dernier:int,pivot)->int:
    # procédure qui place les éléments au début ou à la fin de la liste par comparaison avec le pivot
    echange(L,pivot,dernier)
    j=premier
    for i in range(premier,dernier):
        if L[i]<L[dernier]:
            echange(L,i,j)
            j=j+1
    echange(L,j,dernier)
    return j
## Question 14 
import random
# tri_rapide(list L,int premier,int dernier): trie les termes de la liste L entre premier et dernier inclus
def tri_rapide(L:list,premier:int,dernier:int)->list:
    if len(L)>0 and premier<dernier:
        pivot=random.randint(premier,dernier)
        limite=partitionne(L,premier,dernier,pivot)
        tri_rapide(L,premier,limite-1)
        tri_rapide(L,limite+1,dernier)
    return L
## Test de la fonction `tri_rapide`; **à exécuter sans éditer**
ok=True
if tri_rapide([1,4,3,-1,1,2,3],0,3)!=[-1,1,3,4,1,2,3]: ok=False
if tri_rapide([1,1,1,-1],0,3)!=[-1,1,1,1]: ok=False
if ok:
    print("Fonction tri_rapide: test réussi!")
else:
    print("Fonction tri_rapide: test échoué!")
## Question 15 
import numpy as np
import time
liste_n=[]
liste_temps_tri_rapide=[]
for n in range(1,100002,10000):
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_rapide(liste,0,n-1)
    fin=time.time()
    liste_n.append(n)
    liste_temps_tri_rapide.append(fin-debut)
import matplotlib.pyplot as plt
plt.figure()
plt.plot(liste_n,liste_temps_tri_rapide)
plt.show()
### BILAN ###
## Question 16 
import matplotlib.pyplot as plt
liste_n=[]
liste_temps_tri_par_insertion_dicho=[]
liste_temps_tri_a_peigne=[]
liste_temps_tri_fusion=[]
liste_temps_tri_rapide=[]
for n in range(1,50002,5000):
    liste_n.append(n)
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_par_insertion_dicho(liste)
    fin=time.time()
    liste_temps_tri_par_insertion_dicho.append(fin-debut)
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_a_peigne(liste)
    fin=time.time()
    liste_temps_tri_a_peigne.append(fin-debut)
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_fusion(liste)
    fin=time.time()
    liste_temps_tri_fusion.append(fin-debut)
    liste=list(np.random.randint(0,1000000,n))
    debut=time.time()
    tri_rapide(liste,0,n-1)
    fin=time.time()
    liste_temps_tri_rapide.append(fin-debut)
plt.figure()
plt.plot(liste_n,liste_temps_tri_par_insertion_dicho,label="tri par insertion dichotomique")
plt.plot(liste_n,liste_temps_tri_a_peigne,label="tri à peigne")
plt.plot(liste_n,liste_temps_tri_fusion,label="tri par fusion")
plt.plot(liste_n,liste_temps_tri_rapide,label="tri rapide")
plt.legend()
plt.show()

import matplotlib.pyplot as plt
liste_n=[]
liste_temps_tri_par_insertion_dicho=[]
liste_temps_tri_a_peigne=[]
liste_temps_tri_fusion=[]
liste_temps_tri_rapide=[]
for n in range(1,50002,5000):
    liste_n.append(n)
    liste=list(np.linspace(10000000,0,n))
    debut=time.time()
    tri_par_insertion_dicho(liste)
    fin=time.time()
    liste_temps_tri_par_insertion_dicho.append(fin-debut)
    liste=list(np.linspace(10000000,0,n))
    debut=time.time()
    tri_a_peigne(liste)
    fin=time.time()
    liste_temps_tri_a_peigne.append(fin-debut)
    liste=list(np.linspace(10000000,0,n))
    debut=time.time()
    tri_fusion(liste)
    fin=time.time()
    liste_temps_tri_fusion.append(fin-debut)
    liste=list(np.linspace(10000000,0,n))
    debut=time.time()
    tri_rapide(liste,0,n-1)
    fin=time.time()
    liste_temps_tri_rapide.append(fin-debut)
plt.figure()
plt.plot(liste_n,liste_temps_tri_par_insertion_dicho,label="tri par insertion dichotomique")
plt.plot(liste_n,liste_temps_tri_a_peigne,label="tri à peigne")
plt.plot(liste_n,liste_temps_tri_fusion,label="tri par fusion")
plt.plot(liste_n,liste_temps_tri_rapide,label="tri rapide")
plt.legend()
plt.show()