## Tris quadratiques
import random
import time


## Tests

L10 = [i for i in range(10)]
L1000 = [i for i in range(1000)]
L10000 = [i for i in range(10000)]
A10 = [random.randint(0,10) for i in range(10-1)]
A1000 = [random.randint(0,1000-1) for i in range(1000)]
A10000 = [random.randint(0,10000) for i in range(10000-1)]

def gen_liste(n,N):
    return([random.randint(0,N-1) for i in range(n)])

## Exo 0 : Echange

def echange(L,i,j):
    L[i],L[j] = L[j],L[i]
    return

L = [0,1,2,3,4]
echange(L,1,2)
print(L)

## Exo 3 : Le tri par sélection

def ind_min(L):
    i=0
    for k in range(len(L)):
        if L[k]<L[i]:
            i=k
    return i

def select(L):
    n = len(L)
    for i in range(n-1):
        j=i+ind_min(L[i:])
        echange(L,i,j)
    return

L = [5,1,6,8,4,2,6]
select(L)
print(L)

## Exo 4 :Le tri par insertion

def insere(L):
    for k in range(1,len(L)):
        i = k-1
        while L[k]<L[i] and i>=0:
            i-=1
        # L=L[:i+1]+[L[k]]+L[i+1:k]+L[k+1:]
        # L.insert(i+1,L.pop(k))
        c = L[k]
        for j in range(k,i,-1):
            L[j] = L[j-1]
        L[i+1] = c
    return

L = [2,9,4,56,15,487,5,96,8]
insere(L)
print(L)


## Le tri par insertion revisité

def dico(x,L):
    a = 0
    b = len(L)
    if x < L[0]:
        return 0
    while a < b-1:
        m = (a+b)//2
        if x < L[m]:
            b = m
        else:
            a = m
    return b

# L = [4, 6, 8, 9, 15, 56, 96, 487]
# print([dico(3,L),dico(4,L),dico(5,L),dico(14,L),dico(15,L),dico(4000,L)])


def insere1(L):
    for k in range(1,len(L)):
        i = dico(L[k],L[:k])
        for j in range(k,i,-1):
            L[j],L[j-1] = L[j-1],L[j]
    return

# L = [2,9,4,56,15,487,5,96,8]
# insere(L)
# print(L)
#
#
# L = [2,9,4,56,15,487,5,96,8]
# insere1(L)
# print(L)

## Pour le fun, avec une dichotomie-insertion et les outils de Python

def insere2(L):
    for i in range(1,len(L)):
        x = L[i]
        if L[0] >= x:
            L.insert(0,L.pop(i))
        elif x < L[i-1]:
            k = 0
            l = i-1
            while l-k > 1:
                m = (k + l) // 2
                if L[m] < x:
                    k = m
                else:
                    l = m
            L.insert(k+1,L.pop(i))
    return

# L = [2,9,4,56,15,487,5,96,8]
# insere2(L)
# print(L)

# L = gen_liste(6000,6000)
#
# t1 = time.process_time()
# insere(L)
# print(time.process_time() - t1)
#
# t1 = time.process_time()
# insere1(L)
# print(time.process_time() - t1)
#
# t1 = time.process_time()
# insere2(L)
# print(time.process_time() - t1)



## Exo 5 : Le tri à bulle

def tri_bulle(L):
    for i in range(len(L)-1,-1,-1):
        for j in range(i):
            if L[j] > L[j+1]:
                L[j],L[j+1] = L[j+1],L[j]
    return

# L = [9,4,56,15,487,5,96,8]
# tri_bulle(L)
# print(L)


L = gen_liste(6000,6000)

t1 = time.process_time()
insere(L)
print(time.process_time() - t1)

t1 = time.process_time()
insere1(L)
print(time.process_time() - t1)

t1 = time.process_time()
insere2(L)
print(time.process_time() - t1)

t1 = time.process_time()
tri_bulle(L)
print(time.process_time() - t1)


## Exo 6 : Le tri fusion

def fusion(A,B):
    if len(A)==0:
        return B
    elif len(B)==0:
        return A
    elif A[0]<B[0]:
        return [A[0]]+fusion(A[1:],B)
    else:
        return [B[0]]+fusion(A,B[1:])

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

L = gen_liste(500,5000)
print(L)
t1 = time.process_time()
L = tri_fusion(L)
print(time.process_time() - t1)
print(L)

## Exo 7 : Le tri rapide

def quick(L):
    if len(L)<=1:
        return L
    else:
        G = [l for l in L[1:] if l<=L[0]]
        D = [l for l in L[1:] if l>L[0]]
        return quick(G)+[L[0]]+quick(D)

L = gen_liste(500,5000)
print(L)
t1 = time.process_time()
L = quick(L)
print(time.process_time() - t1)
print(L)


## Exo 8 : Le tri par dénombrement

# On suppose que les entrées sont dans {0,...,k-1}.

def tri_den(A,k):
    C = k*[0]
    for x in A:
        C[x] += 1
    r = 0
    for i in range(0,k):
        for j in range(C[i]):
            A[r+j] = i
        r += C[i]
    return A

L = [0,1,2,6,2,3,5,6,8,9,5,7,5,4,1]
print(tri_den(L,9))

## Exo 9 : Le tri par paquets

p = 10

def gen(n):
    return [random.random() for k in range(n)]

def bucket(L):
    Paquets = [[] for k in range(p)]
    for l in L:
        k = int(l*p)
        Paquets[k].append(l)
    for k in range(p):
        Paquets[k] = quick(Paquets[k])
    L2 = []
    for k in range(p):
        L2+=Paquets[k]
    return L2

L = gen(100)
print(L)
t1 = time.process_time()
L = quick(L)
print(time.process_time() - t1)
print(L)