import sys
import time

from random import *
from multiprocessing import Pool, cpu_count
from pylab import *

p = None

#def qsort1(list):
#    """Implementation de base"""
#
#    if list == []:
#        return []
#    else:
#        pivot = list[0]
#        lesser = qsort1([x for x in list[1:] if x < pivot])
#        greater = qsort1([x for x in list[1:] if x >= pivot])
#        return lesser + [pivot] + greater

def qsort(tpl):
    """Nouvelle implementation avec multiprocessus"""

    l, threaded = tpl
    #threaded est utilisé pour savoir si on doit utiliser Pool.map dans
    #cet appel (ici uniquement le premier appel)

    if l == []:
        return []

    else:
        pivot = l[0]

        u,v = [x for x in l[1:] if x < pivot], [x for x in l[1:] if x >= pivot]

        if threaded: #si premier appel : appel récursif asynchrone sur plusieurs processus
            [lesser, greater] = p.map(qsort, [(u, False), (v, False)])

        else: #si appel récursif : appel récursif normal
            lesser = qsort((u, False))
            greater = qsort((v, False))

    return lesser + [pivot] + greater




if __name__ == "__main__":
    p = Pool(cpu_count())
    a,b,c = map(int, [sys.argv[i] for i in (1,2,3)])
    s = np.arange(a, b, c)
    q = list()
    t = list()

    for j in s:
        l = [i for i in range(j)]
        shuffle(l)
        d = time.time()
        qsort((l, False)) #premier appel avec threaded=False (équivalent à l'algorithme de base)
        e = time.time()
        qsort((l, True))  #premier appel avec threaded=True (utilisation de Pool.map)
        f = time.time()

        q.append(e - d)# temps algo classique
        t.append(f - e)# temps algo parallèle

    grid(True)
    title('[Tri rapide] classique = bleue, parallèle = rouge')
    plot(s, q, color='b')
    plot(s, t, color='r')
    xlabel('Taille de la liste')
    ylabel('Temps (s)')
    show()