# -*- coding: utf-8 -*-
"""
TP11 : Tris

PCSI2 - Albert Schweitzer - Le Raincy
"""

##Listes A executer une seule fois !!
import random as rd
A = list(range(4000))
B = list(range(8000))
rd.shuffle(A)
rd.shuffle(B)

C = list(range(10**4))
for i in range(20):
    a = rd.randint(0, 10**4)
    b = rd.randint(0, 10**4)
    C[a], C[b] = C[b], C[a]

D = list(range(10**4))

##Q2


##Tests

assert not triee(A)
assert not triee(B)
assert not triee(C)
assert triee(D)

##Q3

##Q4

##Q5

##Q6

##Tests

AA = A[:]
tri_selection_iter(AA)
BB = B[:]
tri_selection_iter(BB)
CC = C[:]
tri_selection_iter(CC)
DD = D[:]
tri_selection_iter(DD)
assert triee(AA)
assert triee(AA)
assert triee(AA)
assert triee(AA)

##Q7


##Q8


##Q10

##Q11


##Q12

##Q13

##Tests
import sys
sys.setrecursionlimit(10**5)
AA = A[:]
tri_rapide_place(AA)
BB = B[:]
tri_rapide_place(BB)
CC = C[:]
tri_rapide_place(CC)
DD = D[:]
tri_rapide_place(DD)
assert triee(AA)
assert triee(BB)
assert triee(CC)
assert triee(DD)

##Q14

##Q15

##Tests
assert triee(tri_comptage(A))
assert triee(tri_comptage(B))
assert triee(tri_comptage(C))
assert triee(tri_comptage(D))
##Q16

##Q17

##COMPARATIFS A executer après avoir tout codé
from time import time
import numpy.random as rd
import matplotlib.pyplot as plt

def comparatif_tris(t:int, sel:bool):
    N = [] # liste des tailles
    TR = [] # liste des temps rapide
    TP = [] # liste des temps python
    TC = [] # liste des temps comptage
    if sel:
        TS = [] # liste des temps selection
    n = 10 # taille de la liste à trier
    while n <= t:
        L = rd.randint(0, n+1, n+1)
        debut = time()
        tri_rapide(L)
        fin = time()
        TR.append(fin-debut)
        debut = time()
        sorted(L)
        fin = time()
        TP.append(fin-debut)
        debut = time()
        tri_comptage(L)
        fin = time()
        TC.append(fin-debut)
        if sel:
            debut = time()
            tri_selection_iter(L)
            fin = time()
            TS.append(fin-debut)
        N.append(n)
        n = n + 10
    plt.plot(N, TR, 'g1', label='tri rapide')
    plt.plot(N, TP, '^y', label='python sort')
    plt.plot(N, TC, 'yx', label='tri comptage')
    if sel:
        plt.plot(N, TS, 'bx', label='tri selection')
    plt.legend()
    plt.show()


def comparatif_2(t:int):
    N = [] # liste des tailles
    TR = [] # liste des temps rapide
    TC = [] # liste des temps comptage
    n = 10 # taille de la liste à trier
    while n <= t:
        L = rd.randint(0, 1000, n+1)
        debut = time()
        tri_rapide(L)
        fin = time()
        TR.append(fin-debut)
        debut = time()
        tri_comptage(L)
        fin = time()
        TC.append(fin-debut)
        N.append(n)
        n = n + 10
    plt.plot(N, TR, 'g1', label='tri rapide')
    plt.plot(N, TC, 'yx', label='tri comptage')
    plt.legend()
    plt.show()

def comparatif_3(M:int, sel:bool):
    N = [] # liste des plus grands entiers
    TR = [] # liste des temps rapide
    TC = [] # liste des temps comptage
    if sel:
        TS = [] # liste des temps selection
    n = 10 # taille de la liste à trier
    while n <= M:
        L = rd.randint(0, n, 501)
        debut = time()
        tri_rapide(L)
        fin = time()
        TR.append(fin-debut)
        debut = time()
        tri_comptage(L)
        fin = time()
        TC.append(fin-debut)
        if sel:
            debut = time()
            tri_selection_iter(L)
            fin = time()
            TS.append(fin-debut)
        N.append(n)
        n = n + 10
    plt.plot(N, TR, 'g1', label='tri rapide')
    plt.plot(N, TC, 'yx', label='tri comptage')
    if sel:
        plt.plot(N, TS, 'bx', label='tri selection')
    plt.legend()
    plt.title("Tps de tri d'une liste de 500 entiers entre 0 et n")
    plt.show()