#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Oct 13 15:19:25 2023

@author: matthieu
"""
import numpy as np
import numpy.random as rd
import timeit
import random
import matplotlib.pyplot as plt

from sys import setrecursionlimit
setrecursionlimit(17000)


def partition(L):
    pivot=L[0]
    L1=[]
    L2=[]
    for x in L[1:]:
        if x<pivot:
            L1.append(x)
        else:
            L2.append(x)
    return L1,L2


def tri_rapide(L):
    if len(L)<=1:
        return L
    else:
        L1,L2=partition(L)
        L1t=tri_rapide(L1)
        L2t=tri_rapide(L2)
        return L1t+[L[0]]+L2t
    
    
    
def tempsTri(f,L):
    debut=timeit.default_timer()
    f(L)
    fin=timeit.default_timer()
    return(fin-debut)


def is_sorted(L,reverse=False):
    if not reverse:
        i=0
        while i<len(L)-1 and L[i]<=L[i+1]:
            i=i+1
        return i==len(L)-1
    if reverse:
        i=0
        while i<len(L)-1 and L[i]>=L[i+1]:
            i=i+1
        return i==len(L)-1
    
def tri_rapide2(L):
    if is_sorted(L):
        return L
    elif is_sorted(L,reverse=False):
        return np.reverse(L)
    else:
        return tri_rapide(L)

#%%
L=rd.randint(0,20,128000)
tempsTri(tri_rapide, L)


#%%
N=[]
R=[]
for n in range(1,16,2):
    L=[ random.random()  for i in range(2**n*1000)]
    N.append(2**n*1000)
    R.append(tempsTri(tri_rapide, L))
plt.plot(N,R)
plt.show()


#%%
plt.plot(N,R)
plt.xscale("log")
plt.yscale("log")
plt.show()

#%% limites


L=rd.randint(0,20,16000)
np.flip(L.sort())
tempsTri(tri_rapide, L)