# -*- coding: utf-8 -*-

#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
#                                                                         +
#CORRECTION TD 1 -  ALGORITHMES DE TRI, COMPLEXITE                         +
#                                                                         +
#++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
from numpy.random import random as rd
from numpy.random import randint as rt
from time import time
import matplotlib.pyplot as plt
import numpy as np
from copy import copy

## Q1
#Préliminaires : simulations de choix aléatoires

#QUESTION 1.a.

def alea1(n):
    L=[0]*n
    for i in range(n):
        L[i]=rd()
    return L

#QUESTION 1.b.
def alea2(n,p):
    L=[0]*n
    for i in range(n):
        L[i]=int(p*rd())+1
    return L
#les coefficients de L sont par exemple #choisis entre 0 au sens strict, et p au #sens large
#ou :
def alea2bis(n,p):
    return rt(1,p+1,n)

#QUESTION 1.c.
def alea3(n,p):
    a=time()
    L=[0]*n
    for i in range(n):
        L[i]=int(p*rd())+1
    b = time() - a
    return L, b

## Q2
#Implémentation d'algorithmes de tri

#Une fonction préliminaire d'échange, utilisée dans la suite :
def echange(L,i,j):
    L[i],L[j]=L[j],L[i]

#2.a.   Le tri par sélection en place
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)
    return L

print(Tri_Selection(alea1(20)))

#2.b.   Le tri à bulles
def Tri_Bulle(L):
    fin=False
    while (not fin):
        fin=True
        for i in range(len(L)-1):
            if L[i]>L[i+1]:
               echange(L,i,i+1)
               fin=False
    return L

#2.c.   Le tri par insertion en place

# Inserer a pour fonction d'insérer T[i] à sa place dans T[0...i-1]
def Inserer(T,i) :
    fin=False
    while not fin :
        if i>0 :
            if T[i-1] > T[i] :
                echange(T,i,i-1)
                i=i-1
            else:
                fin=True
        else:
            fin=True

def Tri_Insertion(T) :
    for i in range(1,len(T)):
        Inserer(T,i)
    return T

#2.d.   Le tri fusion

def fusion(L1,L2):
    T=[]
    i,j=0,0
    while i<len(L1) and j<len(L2):
        if L1[i]<L2[j]:
            T.append(L1[i])
            i+=1
        else:
            T.append(L2[j])
            j+=1
    if i<len(L1):
        return T+L1[i:]
    else:
        return T+L2[j:]

def Tri_Fusion(L):
    if len(L)<=1:
        return L
    else:
        return fusion(Tri_Fusion(L[:len(L)//2]),Tri_Fusion(L[len(L)//2:]))

#2.e.   Le tri rapide

def Tri_Rapide(L):
    if L == []:
       return []
    else:
       n = len(L)-1 #on va balayer la liste L et répartir les valeurs
       L1 = []
       L2 = []
       for k in range(1,n+1):
           if L[k]<=L[0]:
              L1.append(L[k]) #L1 reçoit les éléments plus petits
           else:
              L2.append(L[k]) #L2 reçoit les éléments plus grands
       L = Tri_Rapide(L1)+[L[0]]+Tri_Rapide(L2)
    return L

## Q3

#On teste...
Tris = [Tri_Bulle, Tri_Selection, Tri_Insertion, Tri_Fusion, Tri_Rapide]
Noms=['Tri_Bulle', 'Tri_Selection', 'Tri_Insertion', 'Tri_Fusion', 'Tri_Rapide']

#3.a.   Une première fonction de test

def test1(n,A=Tris):
    L=alea2(n,100)
    Copies=[copy(L) for k in range(len(A))]
    for k in range(len(A)):
        Copies[k]=A[k](Copies[k])
    return Copies

#3.b.   Une deuxième...
def test2(N,n,A=Tris):
    +85-
    Temps=[0]*len(A)
    for i in range(N):
        L=alea1(n)
        Copies=[copy(L) for k in range(len(A))]
        for k in range(len(A)):
            depart=time()
            A[k](Copies[k])
            Temps[k]+=time()-depart
    for k in range(len(A)):
        Temps[k]=Temps[k]/N
    return Temps

#3.c.   Et maintenant, on fait un petit dessin
def test3(N=20,nb=51,pas=50,A=Tris,B=Noms):
    X=[100+k*pas for k in range(nb)]
    Z=[[0]*nb for tri in A]
    for k in range(nb):
        Temps=test2(N,X[k])
        for i in range(len(A)):
            Z[i][k]=Temps[i]
    for i in range(len(A)):
        plt.plot(X,Z[i],label=B[i])
    plt.legend(loc='upper left')
    plt.show()

## Q4
#Tri par dénombrement ou par comptage

def tri_denombrement(L,p):
    T=[0]*p
    for n in L:
        T[n]+=1
    L_triee=[]
    for i in range(p):
        L_triee=L_triee+T[i]*[i]
    return L_triee
#pour tester la fonction, par exemple :
A=tri_denombrement(alea2(10000000,100),101)

#Cette méthode de tri n'a d'intérêt que si p est petit devant N.
#Pour p fixé, la complexité est linéaire par rapport à N
#(ie., elle est en O(N)).

## Q5
#Un problème de pesée

#La fonction :
def Roberval(L,T):
    if len(L)==1:
        return T[0]
    elif len(L)==2:
        if L[0]>L[1]:
            return T[1]
        else:
            return T[0]
    else:
        L1,L2,L3=L[:len(L)//3],L[len(L)//3:2*(len(L)//3)],L[2*(len(L)//3):]
        T1,T2,T3=T[:len(L)//3],T[len(L)//3:2*(len(L))//3],T[2*(len(L)//3):]
        m1,m2=sum(L1),sum(L2)
        if m1>m2:
            return Roberval(L2,T2)
        elif m1<m2:
            return Roberval(L1,T1)
        else:
            return Roberval(L3,T3)
#pour tester la fonction, par exemple :
from random import shuffle
#shuffle(L) mélange "au hasard" les coefficients de la liste L

def Test_Roberval(n):
    L=[1]*n
    L[0]=0
    #Le 0 modélise la fausse pièce, les 1 modélisent les vraies
    shuffle(L)
    #On mélange, de sorte que la fausse pièce soit à n'importe quelle place
    x=L.index(0)
    #On triche et l'on regarde où est la fausse pièce
    #(juste pour vérifier que Roberval renvoie le bon résultat)
    return Roberval(L,T),x

def creation(n):
    L=[[0]*n for k in range(n)]
    for i in range(n):
        for j in range(n):
            L[i][j]=j+n*i
    return L