## Imports


from numpy import *
from random import *





    

    


    
## Maximum

def maximum(L):
    """ Cette fonction recherche l'élément maximum (maxi) d’une liste L ainsi que sa place (maxind) dans la liste. Cette fonction renverra maxi et maxind."""
    n=len(L)   # taille de la chaîne
    maxi=L[0]  # premier maximum provisoire
    maxind=0  # Indice correspondant
    for k in range(1,n):
        if L[k]>maxi: # Si l'on rencontre un élément plus grand que le maximum provisoire
            maxi=L[k]  # On a un nouveau maximum provisoire
            maxind=k
    return maxi,maxind
    
    

    
##  Tris

def triselection(L):
    """ Cette fonction trie une liste de nombres L et renvoie la liste triée par sélection """
    n=len(L)
    T=list(copy(L)) # on copie L, on va modifier T
    for k in range(n,0,-1): # n étapes, k va prendre des valeurs de n-1 à 1
        u=maximum(T[:k]) # on récupère le maximum ainsi que son indice dans la partie non triée, ie entre T[0] et T[k-1]
        indmax=u[1]
        a=T[k-1] # on stocke la dernière valeur du tableau
        T[k-1]=u[0] # ou T[indmax]
        T[indmax]=a # on permute le plus grand élément avec le dernier élément
    return T





def triinsertion(L):
    """ Cette fonction trie une liste de nombres L et renvoie la liste triée par la méthode d'insertion """
    n=len(L)
    T=n*[0] #initialisation. On remplit T de 0
    T[0]=L[0]
    for k in range(1,n): # n étapes, k va prendre des valeurs de 1 à n-1
        print("Etape"+str(k)+":")
        Element=L[k]     # C'est l'élément à insérer à l'étape k
        p=k-1  # on va comparer aux éléments placés à la gauche de L[k], ie déjà triés, en l'occurence T[k-1] est le plus grand élément déjà trié
        while p>=0 and T[p]>Element:  # Tant que Element est trop petit, il faut le placer à gauche
            T[p+1]=T[p]  # on décale T[p] vers la droite
            p-=1         # Allons comparer avec l'élément d'avant
            print(T) # Affichage éventuel sur des petites listes pour voir tourner l'algorithme
        T[p+1]=Element  # Au moment où l'on quitte la boucle, on place l'élément T[k] au bon endroit, si T[p] est le premier élément inférieur à Element, c'est qu'Element doit se placer à la place p+1. Notons que cela marche aussi si Element est le plus petit de la liste déjà triée, car dans ce cas on quitte la boucle while avec p=-1, donc T[p+1] correspond à T[0].
        print(T)  # Affichage éventuel sur des petites listes pour voir tourner l'algorithme
    return T
    


    
def tribulle(L):
    """ Cette fonction trie une liste de nombres L et renvoie la liste triée par la méthode du tri par bulle """
    #print(L) # Affichage éventuel sur des petites listes pour voir tourner l'algorithme
    n=len(L)
    T=L[:] # On duplique la liste L
    for j in range(n-1): # on va faire passer la bulle  n-1 fois dans la liste
        print("Etape "+str(j)+":")
        for k in range(n-1-j): # A l'étape j, les j dernières valeurs sont bien triées, car la bulle envoie toujours le plus grand élément au fond de la liste
            if T[k]>T[k+1]: # Si la bulle rencontre deux éléments mal placés
                a=T[k]        # on échange ces deux valeurs. Remarquons que l'instruction T[k],T[k+1]=T[k+1],T[k] convient également
                T[k]=T[k+1]
                T[k+1]=a 
                print(T) # Affichage éventuel sur des petites listes pour voir tourner l'algorithme 
        #print(T) # Affichage éventuel sur des petites listes pour voir tourner l'algorithme
    return T
    







def tribulledrapeau(L):
    """ Cette fonction trie une liste de nombres L et renvoie la liste triée par la méthode du tri par bulle. On améliore cette fonction en utilisant un drapeau qui permet de sortir de la boucle lorsque le tableau est trié. """
    #print(L) # Affichage éventuel sur des petites listes pour voir tourner l'algorithme
    drapeau=1 # initialisation du drapeau
    n=len(L)
    T=L[:] # On duplique la liste L
    j=0 # initialisation de l'indice
    while j<n-1 and drapeau==1: # on va faire passer la bulle au plus n-1 fois dans la liste
        drapeau=0 # on baisse le drapeau. Si lors de la boucle suivante, on ne rentre pas dans l'instruction if, c'est que la liste est triée, on peut donc quitter la boucle while
        print("Etape "+str(j)+":")
        for k in range(n-1-j): # A l'étape j, les j dernières valeurs sont bien triées, car la bulle envoie toujours le plus grand élément au fond de la liste
            if T[k]>T[k+1]: # Si la bulle rencontre deux éléments mal placés
                drapeau=1 # Le tri n'étant pas fini, il faut poursuivre le passage de la bulle, on relève le drapeau
                a=T[k]        # on échange ces deux valeurs. Remarquons que l'instruction T[k],T[k+1]=T[k+1],T[k] convient également
                T[k]=T[k+1]
                T[k+1]=a
                print(T,drapeau) # Affichage éventuel sur des petites listes pour voir tourner l'algorithme
        j+=1
    return T,drapeau


def tri_par_comptage(L):
    """ Cette fonction trie une liste L d'entiers entre 0 et M=Max(L) par la méthode du comptage. On compte le nombre d'occurences de chaque valeur de L, puis on crée la liste triée """
    n=len(L)
    M=max(L) # détermination du maximum
    Occ=(M+1)*[0]
    for x in L:
        Occ[x]+=1
    T=[]
    for k in range(M+1):
        T=T+Occ[k]*[k]
    return T
## Recherche dichotomique

def recherchetriliste(L,x):
    """ Cette fonction recherche un élément x dans une liste L. Elle renvoie un indice correspondant à la place de x dans L, False si x n'est pas dans L. On suppose ici que la liste L est triée. """
    n=len(L) # taille de la liste
    gauche=0 # extrémité gauche de la liste L
    droite=n-1 # extrémité droite de la liste L
    milieu=(gauche+droite)//2
    while gauche<=droite:
        if L[milieu]==x: # Trouvé !
            return milieu
        elif L[milieu]<x: # x se trouve dans la partie droite de la liste
            gauche=milieu+1
        else: # x se trouve dans la partie gauche de la liste
            droite=milieu-1
        milieu=(gauche+droite)//2 # calcul du nouveau milieu
    return False
            

    
##  Calcul de la médiane

def mediane(L):
    """ Cette fonction renvoie la médiane d'une liste L donnée """
    T=tribulledrapeau(L) # On commence par trier la liste. Si c'est déjà le cas, cela va très vite avec notre dernière fonction.
    n=len(L)
    if n/2!=n//2: # Si n est impair
        milieu=int((n-1)/2)  # On définit l'indice de milieu de liste. On pense à typer la variable (int) car les indices ne peuvent être que des entiers (sauf ordinateurs mutants...)
        return(T[milieu]) # Un seul individu médian
    else:
        milieu=int(n/2)
        return (T[milieu-1]+T[milieu])/2 # On a deux individus médians, la médiane correspond à la moyenne de ces deux valeurs
        
def medianeeffectif(L,E):
    """ Cette fonction renvoie la médiane d'une liste de nombres L associée à une liste E correspondants aux effectifs de chaque modalité de L """
    n=len(L)
    GL=[] # On va fabriquer une liste GL, contenant les éléments de L, chacun d'entre eux étant répété un nombre de fois correspondant à son effectif  
    for k in range(n):
        GL+=E[k]*[L[k]]  # Chaque élément de L est ainsi dupliqué E[k] fois
    print(GL)            # on peut afficher cette nouvelle liste, ce n'est pas obligatoire
    return mediane(GL)     # On calcule la mediane grâce à la fonction précédente