#!/usr/bin/python3 -B




## Question 2.1



def compare_et_échange_classique(L,i):
    if L[i] > L[i+1] :
        temp = L[i]
        L[i] = L[i+1]
        L[i+1] = temp

def compare_et_échange(L,i):
    if L[i] > L[i+1] :
        (L[i] , L[i+1]) = (L[i+1] , L[i])

## Question 2.2

def passe_tri_bulles(L,k):
    n = len(L)
    for i in range(n-k):
        compare_et_échange(L,i)


## Question 2.3

def tri_bulles(L):
    n = len(L)
    for k in range(1,n): # de 1 à n-1
        passe_tri_bulles(L,k)

print("\nExercice 2\n")

from random import randint # À mettre au début du fichier
L = [ randint(1,100) for x in range(20) ]
print("Avant :", L)
tri_bulles(L)
print("Après :", L)

## Question  2.4

# On retourne True s’il y a eu un échange
def compare_et_échange2(L,i):
    if L[i] > L[i+1] :
        L[i] , L[i+1] = L[i+1] , L[i]
        return True
    else:
        return False

# On retourne True s’il y a eu un échange
def passe_tri_bulles2(L,k):
    changement=False
    for i in range(len(L)-k):
        b=compare_et_échange(L,i)
        changement = changement or b
    return changement

def tri_bulles2(L) :
    for k in range(1,len(L)) :
        b=passe_tri_bulles2(L,k)
        if b==False:
            return # S’il n'y a eu aucun changement on s'arrête

L = [ randint(1,100) for x in range(20) ]
print("Avant :", L)
tri_bulles2(L)
print("Après :", L)




print("\nExercice 3\n")

## Question 3.1

def liste_nombre_occurrences(L):
    n = max(L) + 1 # vous devez savoir écrire max !
    N = [0]*n
    for i in range(len(L)):
        e = L[i] # On trouve un e -> on incrément N[e]
        N[e] = N[e] + 1
    return N


## Question 3.2


def crée_liste_triée_inefficace(N):
    Lt = []
    for j in range(len(N)):
        k = N[j] # j doit être présent k fois dans la liste Lt
        Lt = Lt + [j] * k
    return Lt


def crée_liste_triée(N):
    Lt = []
    for j in range(len(N)):
        k = N[j] # j doit être présent k fois dans la liste Lt
        for choucroute in range(k):# choucroute n’est jamais utilisée.
            Lt.append(j)
    return Lt


## Question 3.3

# On utilise deux indices j pour N  :  N[j] et
#                         i pour Lt : Lt[i]
# j est géré par une boucle for
# i est géré manuellement.
def crée_liste_triée_efficace(N):
    Lt = [0] * sum(N)
    i=0
    for j in range(len(N)):
        k = N[j]
        for _ in range(k): # plutôt que de définir une variable choucroute inutile, on
            Lt[i] = j      # peut la remplacer par « _ ». La variable n'a plus de nom
            i = i+1
    return Lt


## Question 3.4

def tri_comptage(L):
    N = liste_nombre_occurrences(L)
    Lt = crée_liste_triée_inefficace(N)
    return Lt

L = [ randint(1,4) for x in range(20) ]
print("Avant :", L)
L = tri_comptage(L)
print("Après :", L)



def tri_comptage(L):
    N = liste_nombre_occurrences(L)
    Lt = crée_liste_triée(N)
    return Lt

L = [ randint(1,4) for x in range(20) ]
print("Avant :", L)
L = tri_comptage(L)
print("Après :", L)


def tri_comptage(L):
    N = liste_nombre_occurrences(L)
    Lt = crée_liste_triée_efficace(N)
    return Lt

L = [ randint(1,4) for x in range(20) ]
print("Avant :", L)
L = tri_comptage(L)
print("Après :", L)


print('\nExercice 4\n')

## Question 4.1




## Question 4.2

# La fonction échange n'est pas indispensable mais elle permet de gagner en
# lisibilité

def échange(L,i,j):
    (L[i], L[j]) = (L[j], L[i])

def tri_hollandais(L):
    n = len(L)
    (b,i,r) = (0,0,n)
    print(L)
    while (i<r) :
        if L[i] == 'B' :
            échange(L,i,b)
            i = i+1
            b = b+1
        elif L[i] == 'R' :
            échange(L,i,r-1)
            r = r-1
        else :
            i = i+1
        print(L)

dico = { 1:"B", 2:"W", 3:"R"}
L = [ dico[randint(1,3)] for x in range(20) ]
tri_hollandais(L)




print('\nExercice 5\n')

## Question 5.1


def fusion(L1,L2) :
    if L1 == [] :
        return L2
    elif L2 == [] :
        return L1
    elif L1[0] < L2[0] :
        return [L1[0]] + fusion( L1[1:] , L2 )
    else :
        return [L2[0]] + fusion( L1 , L2[1:] )

def fusion2(L1,L2) :
    i = 0 # indice dans L1
    j = 0
    # On commence par créer une liste de la bonne taille
    n = len(L1) + len(L2)
    L = [0] * n
    # On aura trois indices
    i=0 # pour L1
    j=0 # pour L2
    for k in range(n) : # pour L
        # Si on a ajouté tous les élèments de L1
        # on ajoute alors ceux de l2
        if i == len(L1) :
            L[k] = L2[j]
            j = j+1
        # Si on a ajouté tous les élèments de L2
        # on ajoute alors ceux de l1
        elif j == len(L2) :
            L[k] = L1[i]
            i = i+1
        # Sinon on ajoute le plus petit élèment
        # entre L1[i] et L1[j]
        else :
            if L1[i] > L2[j] :
                L[k] = L2[j]
                j = j+1
            else :
                L[k] = L1[i]
                i = i+1
    return L


def fusion3(L1,L2) :
    res = []
    while True : # On s'arrête quand L1 ou L2 est vide
        if L1 == [] :
            return res + L2
        if L2 == [] :
            return res + L1
        else :
            if L1[0] < L2[0] :
                n = L1.pop(0)
            else :
                n = L2.pop(0)
            res.append(n)


## Question 5.2




def tri_fusion(L):
    if len(L) < 2:
        return L
    m = len(L)//2
    L1 = tri_fusion(L[:m])
    L2 = tri_fusion(L[m:])
    return fusion(L1,L2)


L = [ randint(1,100) for x in range(20) ]
print("Avant :", L)
L = tri_fusion(L)
print("Après :", L)



def tri_fusion2(L):
    if len(L) < 2:
        return L
    m = len(L)//2
    L1 = tri_fusion2(L[:m])
    L2 = tri_fusion2(L[m:])
    return fusion2(L1,L2)

L = [ randint(1,100) for x in range(20) ]
print("Avant :", L)
L = tri_fusion2(L)
print("Après :", L)


def tri_fusion3(L):
    if len(L) < 2:
        return L
    m = len(L)//2
    L1 = tri_fusion3(L[:m])
    L2 = tri_fusion3(L[m:])
    return fusion3(L1,L2)

L = [ randint(1,100) for x in range(20) ]
print("Avant :", L)
L = tri_fusion3(L)
print("Après :", L)


print('\nExercice 6\n')
## Question 6-1


# Cours 2 !

def puissance_rapide(a,n):
    if n == 0:
        return 1
    elif n%2 == 0:
        return puissance_rapide(a,n//2) ** 2
    else:
        return a * puissance_rapide(a,n//2) ** 2

for n in range(11):
    un = puissance_rapide(1,n)
    deux = puissance_rapide(2,n)
    dix = puissance_rapide(10,n)
    print(f"{un}, {deux:>4}, {dix}")


print('\nExercice 7\n')


print("Question 7.1")
def recherche_dichotomique_erronée(x,L) :
    # On ajoute une variable pour s’arrêter automatiquement au bout de
    # 10 passages.
    nb_de_passage=0
    g = 0
    d = len(L) - 1
    while g != d :
        m = (g + d) // 2

        nb_de_passage = nb_de_passage + 1
        print(f"passage {nb_de_passage:0>2} : g={g}, d={d}, m={m} et L[m]={L[m]}")
        if nb_de_passage > 10:
            return

        if L[m] == x :
            return m
        elif L[m] < x :
            g = m
        else :
           d = m
    if L[g] == x :
        return g
    return -1


recherche_dichotomique_erronée(7 ,[i for i in range(2,21,2)])




print("\nQuestion 7.2")



def recherche_dichotomique(x,L) :
    # On ajoute une variable pour s’arrêter automatiquement au bout de
    # 10 passages.
    nb_de_passage=0
    g = 0
    d = len(L) - 1
    while g < d -1 :
        m = (g + d) // 2

        nb_de_passage = nb_de_passage + 1
        print(f"passage {nb_de_passage:0>2} : g={g}, d={d}, m={m} et L[m]={L[m]}")

        if L[m] == x :
            return m
        elif L[m] < x :
            g = m
        else :
           d = m
    if L[g] == x :
        return g
    return -1


d = recherche_dichotomique(7 ,[i for i in range(2,21,2)])
print(d)