#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Oct  4 08:55:43 2023

@author: matthieu
"""

import numpy.random as rd
import timeit
import random
import matplotlib.pyplot as plt




def decale_et_insere(L,i):
    '''insère l’élément L[i] à la bonne place dans la partie (déjà triée) à sa gauche'''
    
    ind=i
    valeur=L[i]
    while ind > 0 and valeur <=L[ind-1]:
        L[ind]=L[ind-1]
        ind=ind-1
    L[ind]= valeur 
    
    
def triinsertion(L):
    ''' tri par insertion, en place'''
    for i in range(1,len(L)):
        decale_et_insere(L,i)
        
#%%


L=rd.randint(0,20,100)
print(L)
triinsertion(L)
print(L)




#%%

def indice_du_plus_petit(liste,deb):
    '''renvoie l’indice du plus petit élément présent dans la partie non encore triée, c’est-à-dire parmi les
éléments d’indices deb à la fin'''
    imin=deb
    for i in range(deb, len(liste)):
        if liste[imin]>liste[i]:
            imin=i
    return imin

#%%
indice_du_plus_petit([1,2,-1,5,6,8,0],3)


def triselection(L):
    for i in  range(len(L)-1):
        imin=indice_du_plus_petit( L,i)
        L[imin],L[i]=L[i],L[imin]
            
#%%


L=rd.randint(0,20,100)
print(L)
triselection(L)
print(L)
            



#%%


def echange_voisin(L,k):
    for i in range(k):
        if L[i]>L[i+1]:
            L[i],L[i+1]=L[i+1],L[i]
        
def TriBulle(L):
    for k in range(len(L)-1,0,-1):
        echange_voisin(L, k)
        
        
        
#%%


L=rd.randint(0,20,100)
print(L)
TriBulle(L)
print(L)
            


#%%


def tempsTri(f,L):
    debut=timeit.default_timer()
    f(L)
    fin=timeit.default_timer()
    return(fin-debut)


#%%   

L=rd.randint(0,20,10000)
tempsTri(TriBulle, L)


#%
N=[]
Ri=[]
Rs=[]
Rb=[]
for n in range(1,5):
    L=[ random.random()  for i in range(2**n*1000)]
    N.append(2**n*1000)
    Ri.append(tempsTri(triinsertion,L) )
    Rs.append(tempsTri(triselection,L) )
    Rb.append(tempsTri(TriBulle,L) )
plt.plot(N,Ri)
plt.plot(N,Rs)
plt.plot(N,Rb)
plt.show()
    
#%%
plt.plot(N,Ri)
plt.plot(N,Rs)
plt.plot(N,Rb)
plt.xscale("log")
plt.yscale("log")
plt.show()