#exercice 1
def recherche_min_mot(L):
    n=len(L)
    nblettres = len(L[0])
    indice = 0
    for i in range(1, n):
        if len(L[i]) < nblettres:
            nblettres = len(L[i])
            indice = i
    return indice
    
def tri_selection_mot(L):
    for i in range(len(L)):
        nblettres = len(L[i])
        indice = i
        for j in range(i+1, len(L)):
            if len(L[j]) < nblettres:
                nblettres = len(L[j])
                indice = j
        L[indice], L[i] = L[i], L[indice]
    return L
    


# exercicie 2
# tri fusion
def fusionner(A: list, B:list) -> list:
    if len(A) == 0:	# liste vide
        return B
    if len(B) == 0: 
        return A
    if A[0] <= B[0]:
        return [ A[0] ] + fusionner( A[1:], B)
    else:
        return [ B[0] ] + fusionner( A, B[1:])

# def tri_fusion(L: list) -> list:
# alphabet.index('a)


from random import *
L=[]
for i in range(3000):
    L.append(randint(1,1001))
    
L=[randint(1,1001) for i in range(3000)]
    


#exercice 3
    
alphabet='AaBbCcDdEeéèDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz'

def ordre_alphabetique(c1, c2):
    if alphabet.index(c1) < alphabet.index(c2):
        return -1
    elif alphabet.index(c2) < alphabet.index(c1):
        return 1
    else:
        return 0
    
def ordre_lexicographique(m1, m2):
    n=min(len(m1), len(m2))
    for i in range(n):
        if ordre_alphabetique(m1[i], m2[i])== 1:
            return 1
        elif ordre_alphabetique(m1[i], m2[i])== -1:
            return -1
    if len(m1) < len(m2):
        return -1
    elif len(m2) < len(m1):
        return 1
    else:
        return 0
        
def tri_lexicographique(L):
    for i in range(len(L)):
        j = i
        k = L[i]
        while j > 0 and ordre_lexicographique(k,L[j - 1])== -1 :
            L[j] = L[j-1]
            j = j - 1
        L[j] = k
        
mots= ['bon', 'toi', 'bonjour', 'oui']
tri_lexicographique(mots)
print(mots)


    
    
#exercice 4

def distance2(point):
    return (point[0])**2+(point[1])**2
    
    
    
    
def compare(p1, p2):
    d1=distance2(p1)
    d2=distance2(p2)
    if d1 < d2:
        return -1
    elif d2 < d1:
        return 1
    else:
        return 0

def tri_points(L):
    n = len(L)
    for i in range(n-1):
        m = L[i]
        pos = i
        for j in range(i, n):
            if compare(L[j], m)==-1 :
                m = L[j]
                pos = j
        L[i], L[pos] = L[pos], L[i]
    return L
    
    
# Exercice 4

# Q1
def indice_max(C, j):
    """ renvoie l'indice du max de C[:j] """
    m = C[0]
    pos = 0
    for i in range(j):
        if C[i] > m:
            m = C[i]
            pos = i
    return pos
    
#Q2
def retourner(C, j):
    """ retourne C[:j+1] dans C """
    for k in range(j//2 + 1):
        C[k], C[j - k] = C[j - k], C[k]
    return C
        
#Q3

def tri_crepes(C: list) -> None:
    n = len(C)
    while n > 1:
        p = indice_max(C, n)
        retourner(C, p)
        retourner(C, n-1)
        n = n - 1