## 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 1 : 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 2 :Le tri par insertion

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

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


## Exo 3 :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 4 :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)

## 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))