# -*- coding: utf-8 -*-
"""
Created on Wed Sep 30 23:34:56 2015

@author: dconduche
"""

import numpy as np
import time as t
import matplotlib.pyplot as plt

""" Exercices 1 et 2 : Préliminaires """


def chronometre(fonction, arg_fonc):
    debut = t.time()
    fonction(arg_fonc)
    fin = t.time()
    return fin - debut


def liste_hasard1(n, maxi=100):
    L = []
    for i in range(n):
        L.append(np.random.randint(maxi))
    return L


def liste_hasard2(n, maxi=100):
    return [np.random.randint(maxi) for i in range(n)]


def liste_hasard(n, maxi=100):
    return list(np.random.randint(0, maxi, n))


### Tests :
#print(chronometre(t.sleep, 2))
#print(liste_hasard(10, 20))
#print(liste_hasard(10))


""" Exercice 3 : Tri par insertion """


def tri_insertion(L):
    for i in range(1, len(L)):
        j = i
        v = L[i]
        while (j > 0) and (L[j-1] > v):
            L[j] = L[j-1]
            j = j-1
        L[j] = v
    return None


def tri_insertion_verbeux(L):
    print('Liste de départ', L)
    for i in range(1, len(L)):
        j = i
        v = L[i]
        print('----entrée dans while----')
        print('i = ', i, ', v = L[i] = ', v)
        while (j > 0) and (L[j-1] > v):
            L[j] = L[j-1]
            j = j-1
            print('while étape j = ', j)
            print(L)
        L[j] = v
        print(L)
        print('----sortie de while----')
    return None

#L = liste_hasard(10, 20)
#tri_insertion_verbeux(L)


def echantillon(n_max, nb_n, nb_listes, fonction_tri=tri_insertion, tri=False):
    """Teste la fonction tri sur un certain nombre de listes au hasard.
    :param n_max: valeur maximale de la taille de la liste
    :param nb_n: nombres de n testés
    :param nb_listes: nombre de listes testées pour chaque n (pour lisser)
    :param fonction_tri: la fonction que l'on teste
    :param tri: si la liste doit être déjà triée
    :return: un couple de listes. La liste des tailles testée, et la liste des
    temps
    """
    maxi = 10**6
    pas = n_max // nb_n
    liste_n = []
    liste_temps = []
    for i in range(nb_n):
        n = (i+1) * pas
        temps = 0
        for j in range(nb_listes):
            L = liste_hasard(n, maxi)
            if tri:
                L.sort()
            temps += chronometre(fonction_tri, L)
        liste_temps.append(temps/nb_listes)
        liste_n.append(n)
    return liste_n, liste_temps


def tri_python(L):
    L.sort()
    return None
#n_max = 1000
#x, y_inser = echantillon(n_max, 20, 10)
#x, y_sort = echantillon(n_max, 20, 10, tri_python)
#plt.plot(x, y_inser)
#plt.plot(x, y_sort)
#plt.show()


""" Exercice 4 : Quicksort """


def quicksort(L):
    if len(L) <= 1:
        return L
    else:
        pivot = L[0]
        plus_grand = []
        plus_petit = []
        for x in L[1:]:
            if x >= pivot:
                plus_grand.append(x)
            else:
                plus_petit.append(x)
        return quicksort(plus_petit) + [pivot] + quicksort(plus_grand)


def quicksort_al(L):
    """Quicksort avec pivot aléatoire"""
    if len(L) <= 1:
        return L
    else:
        k = np.random.randint(len(L))
        pivot = L.pop(k)
        plus_grand = []
        plus_petit = []
        for x in L[1:]:
            if x >= pivot:
                plus_grand.append(x)
            else:
                plus_petit.append(x)
        return quicksort_al(plus_petit) + [pivot] + quicksort_al(plus_grand)


""" Exercice 5 : avec un compteur """

### Avec des compteurs : on modifie la fonction de comparaison >=
# Cf autre fichier


""" Exercice 6 : Fusion"""


def fusion(L1, L2):
    """fusionne deux listes triées"""
    if L1 == []:
        return L2
    if L2 == []:
        return L1
    #Désormais, les deux listes sont non vides.
    if L1[0] < L2[0]:
        return [L1[0]] + fusion(L1[1:], L2)
    else:
        return [L2[0]] + fusion(L1, L2[1:])


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


"""Tests"""


def comparaison_qck_srt():
    """Comparaison quicksort / sort"""
    n_max = 10**5
    x, y_quick = echantillon(n_max, 20, 10, quicksort)
    x, y_sort = echantillon(n_max, 20, 10, tri_python)
    plt.plot(x, y_quick, label="quick")
    plt.plot(x, y_sort, label="python")
    plt.legend()
    plt.show()
#comparaison_qck_srt()
### Comparaison insertion / quicksort:
#n_max = 200
#x, y_inser = echantillon(n_max, 10, 1000)
#x, y_quick = echantillon(n_max, 10, 1000, quicksort)
#plt.plot(x, y_inser, c="blue")
#plt.plot(x, y_quick, c="green")
#plt.legend(["i", "q"])
#plt.show()


### Comparaison quicksort / quicksort pivot aléatoire, sur une liste triée: