################################################################################
#                   DS 5 d'informatique de l'année 2024/2025                   #
#                          MPSI - Algorithmes de tri                           #
#                                  Correction                                  #
################################################################################

################
### Question 1.a
################

import random
import time

################
### Question 1.b
################

from math import floor

################
### Question 1.c
################

import matplotlib.pyplot as plt

################
### Question 2
################

def phi(L):
    C = [0] * 101
    for i in range(len(L)):
        C[L[i]] += 1
    return C

################
### Question 4.a
################

def triComptage(L):
    C = phi(L)
    M = []
    for i in range(len(C)):
        for _ in range(C[i]):
            M.append(i)
    return M

################
### Question 5.a
################

def intToBin(n):
    assert n >= 0
    s = ""
    while n > 0:
        if n % 2 == 0:
            s += "0"
        else:
            s += "1"
        n = n // 2
    return s

################
### Question 5.b
################

def listToBin(L):
    M = []
    for n in L:
        M.append(intToBin(n))
    return M

################
### Question 6.a
################

def tailleMax(M):
    maxi = -1
    for s in M:
        if len(s) > maxi:
            maxi = len(s)
    return maxi

################
### Question 6.b
################

def completer(M):
    m = tailleMax(M)
    N = []
    for s in M:
        N.append(s + "0" * (m - len(s)))
    return N

################
### Question 7.a
################

def separerBit(N, i):
    N0 = []
    N1 = []
    for s in N:
        if s[i] == "0":
            N0.append(s)
        elif s[i] == "1":
            N1.append(s)
    return N0, N1

################
### Question 7 (solution 1)
################

def triBinStr_rec0(N, i):
    if i == -1:
        return N[:]
    N1, N2 = separerBit(N, i)
    return triBinStr_rec0(N1, i-1) + triBinStr_rec0(N2, i-1)

def triBinStr_rec(N):
    if len(N) == 0:
        return []
    else:
        return triBinStr_rec0(N, len(N[0]) - 1)

################
### Question 7 (solution 2)
################

def triBinStr_it(N):
    if len(N) == 0:
        return []
    for i in range(len(N[0])):
        N0, N1 = separerBit(N, i)
        N = N0 + N1
    return N

################
### Question 8.a
################

def binToInt(s):
    n = 0
    for i in range(len(s)):
        if s[i] == "1":
            n += 2**i
    return n

################
### Question 8.b
################

def triBin(L):
    M = listToBin(L)
    N = completer(M)
    S = triBinStr_it(N)
    T = []
    for s in S:
        T.append(binToInt(s))
    return T

################
### Question 9
################

def peigne(L, p):
    assert p > 0
    b = False
    for i in range(len(L) - p):
        if L[i] > L[i+p]:
            L[i], L[i+p] = L[i+p], L[i]
            b = True
    return b

################
### Question 10.c
################

def triPeigne(L, R):
    p = len(L)
    b = True
    while p > 1 or b:
        p = max(1, floor(p / R))
        b = peigne(L, p)

################
### Question 11.b
################

L = [1, 5, 2, -5]
triPeigne(L, 1.05062025)
print(L)

################
### Question 12
################

def listeAlea():
    L = []
    for _ in range(random.randint(500, 1000)):
        L.append(random.randint(-1000, 1000))
    return L

################
### Question 13
################

def chrono(R):
    T = 0
    for _ in range(800):
        L = listeAlea()
        t_ini = time.perf_counter()
        triPeigne(L, R)
        T += time.perf_counter() - t_ini
    return T

################
### Question 14
################

def traceChrono(a, b, m):
    pas = (b-a)/(m-1)
    X = [a + i*pas for i in range(m)]
    Y = []
    for R in X:
        Y.append(chrono(R))
    plt.figure()
    plt.plot(X, Y, "o", color = "black")
    plt.show()

################
### Question 16.a
################

def indiceMin(P):
    i_min = None
    for i in range(len(P)):
        if P[i] != None:
            if i_min == None or P[i_min] > P[i]:
                i_min = i
    return i_min

################
### Question 16.b
################

def bornes(L):
    i = indiceMin(L)
    M = [-e for e in L]
    j = indiceMin(M)
    return L[i], L[j]

################
### Question 17.a
################

def copie(L):
    return L[:]

################
### Question 18.b
################

def partition(L, m):
    a,b = bornes(L)
    P = [[] for _ in range(m)]
    for x in L:
        i = floor((x-a)*m/(b-a))
        if i == m:
            i = m-1
        P[i].append(x)
    return P

################
### Question 19
################

def triPaquets(L, m):
    # Liste vide
    if L == []:
        return copie(L)
    # Listes dont tous les éléments sont égaux
    a,b = bornes(L)
    if a == b:
        return copie(L)
    # Listes avec au moins deux éléments distincts
    P = partition(L, m)
    T = []
    for i in range(m):
        for _ in range(len(P[i])):
            k = indiceMin(P[i])
            T.append(P[i][k])
            P[i][k] = None
    return T