# -*- coding: utf-8 -*-
"""
Created on Tue Dec 31 11:28:42 2024

@author: arnau
"""

import numpy as np
import matplotlib.pyplot as plt
import numpy.random as rd
from time import time

#%% Tri par comptage

def tri_comp(L):
    n = len(L)
    C = [0 for _ in range(n)]
    for i in range(n):
        s = 0      # compteur nombre d'occurence
        n = 0      # compteur de position
        for x in L:
            if x<L[i]:
                n +=1
            elif x==L[i]:
                s+=1
        for k in range(s):
            C[n+k]=L[i]
    return C



#%% Tri insertion

def tri_insertion(L):
    n = len(L)
    C = [L[0]]
    for i in range(1,n):
        j=0
        while  j<len(C) and C[j]<L[i]:
                j+=1
        C.insert(j,L[i])
    return C
        
#%% Tri sélection

def indic_max(L,n):
    max = L[0]
    ind = 0
    for i in range(n):
        if L[i]>max:
            max = L[i]
            ind = i
    return ind

def tri_selection(L):
    C = L
    for k in range(len(L)):
        ind = indic_max(C,len(L)-k)
        C[len(L)-k-1],C[ind] = C[ind],C[len(L)-k-1]
    return C

#%% Tri fusion

def diviser(L):
    gauche = []
    droite = []
    for k in range(1,len(L)):
        if L[k]<L[0]:
            gauche.append(L[k])
        else:
            droite.append(L[k])
    return gauche, droite

def tri_fusion(L):
    if len(L)<=1:
        return L
    else:
        gauche,droite = diviser(L)
        return tri_fusion(gauche)+[L[0]]+tri_fusion(droite)


#%% Tests

L = [12,-3,17,9,1] 
test = [3.5,-2.1,4,-2.1,0,1,1,9,8,4,-2]
test2 = [10,1,5,19,3,3,2,17]
test3 = [12,12,10,1,0,0,12,-3,1,1,-2,-2,17]


#%% Vitesse

def liste_alea(n):
    '''
   Liste aléatoire d'entiers
    '''
    return [rd.randint(1,5*n+1) for k in range(n)]


def vitesse ( fct , L ) :
    '''
    calcul le temps d'exécution de la fonction de tri fct sur la liste L
    '''
    debut = time ()
    fct ( L )
    fin = time ()
    return ( fin - debut )

def Temps_moyen(fct,n):
    '''
    temps moyen (sur 10 tests) de tri d'une liste aléatoire de longueur n par la fonction de tri fct
    '''
    t = 0
    for _ in range(10):
        t += vitesse(fct,liste_alea(n))
    return t/10

#N = [10,50,100,200,400,600,800,1000,1400,1600,1800,2000]
N = [10,50,100,1000,2000]

# Comparaison des temsp d'exécution des différentes méthodes de tris en fonction de la taille de la liste à trier
temps_insertion = []
temps_selection = []
temps_fusion = []
for n in N:
    temps_insertion.append(Temps_moyen(tri_insertion,n))
    temps_selection.append(Temps_moyen(tri_selection,n))
    temps_fusion.append(Temps_moyen(tri_fusion,n))
plt.plot(N,temps_insertion, label='tri insertion')
plt.plot(N,temps_selection, label='tri selection')
plt.plot(N,temps_fusion, label='tri fusion')
plt.xlabel('Taille de la liste')
plt.ylabel('Temps d exécution')
plt.legend()