# -*- coding: utf-8 -*-
"""
TP7 : Boucle imbriquées

PCSI2 - Albert Schweitzer - Le Raincy
"""

##Q2

mon_fichier = open('TP7.txt', 'w')
mon_fichier.write('CRETOIS\nREMI\n01011900')
mon_fichier.close()

##Q4

def recherche_motif(motif:str, texte:str):
    '''
    Renvoie la position de la première apparition de motif dans texte, ou None sinon
    '''
    for i in range(len(texte) - len(motif)):
        j = 0
        while j < len(motif) and motif[j] == texte[i+j]:
            j = j + 1
        if j == len(motif):
            return i
    return None

##Q5

fichier = open('roman.txt', 'r')
texte = fichier.read()
motif = "l'ami\nConseil n'a rien à dire"
pos = recherche_motif(motif, texte)
if pos == None:
    print(motif, ' napparait pas dans le texte')
else:
    print(motif, ' est en position ', pos)
fichier.close()
##Q6-Q7

'''
Dans le pire des cas, on va répéter aller jusqu'au bout de l'exécution de la boucle while et de la boucle for : par exemple, texte = 'aaaaaaaa' et motif = 'aaab'.
La complexité est O(len(motif)*(len(texte)-len(motif)))
'''

##Q8

def echange(L:list, i:int) -> None:
    '''
    Echange les éléments L[i] et L[i+1]
    '''
    L[i], L[i+1] = L[i+1], L[i]

##Q9-10

def parcours(L:list) -> None:
    '''
    Parcourt la liste L une fois et
    fait les échanges nécessaires
    '''
    for i in range(len(L)-1):
        if L[i] > L[i+1]:
            echange(L, i)

##Q11
'''
On peut raisonner par l'absurde : si le maximum n'est pas
en dernière position, alors il est en position i, mais
lors de l'exécution de parcours, il aurait du être
échangé avec L[i+1].
On peut aussi utiliser un invariant de boucle : L[i] est le maximum de la liste L[:i+1]
Avant la boucle, L[0] est bien le plus grand dans L[:1] = [L[0]].
Supposons qu'avant l'itération i, l'invariant est vrai.
Alors
-soit L[i] > L[i+1] et donc L[i] est le plus grand de L[:i+2] (par HR) et va être placé en position i+1
-soit L[i] <= L[i+1] et donc L[i+1] est le plus grand de L[:i+2] (par HR) et est déjà en position i+1
La propriété est vraie à la fin de l'itération i.
'''

##Q12
'''
Si on exécute une fois parcours, après len(L)-p itération dans parcours, L[len(L)-p] sera le plus grand élément de L[:len(L)-p+1] et plus petit que les p derniers éléments. Les dernières itérations de parcours ne changeront rien car les p derniers
sont déjà triés. Donc on aura que les p+1
derniers éléments seront au bon endroit.
'''

##Q13
'''
Par récurrence on aura donc après p exécutions de parcours, les p derniers éléments de L sont au bon endroit. Donc après len(L) exécutions, L est triée.
'''

##Q14

def tri_a_bulles(L:list) -> None:
    '''
    Trie la liste L en utilisant le tri à bulles
    '''
    for i in range(len(L)):
        parcours(L)

L = [1,2,3,4,5]
tri_a_bulles(L)
print(L)
M = [4,3,2,1]
tri_a_bulles(M)
print(M)


##Q15-16-17
from time import process_time
import random as rd

L = [rd.randint(0, 99) for i in range(1000)]

debut = process_time()
tri_a_bulles(L)
fin = process_time()
print(fin-debut)

L = [rd.randint(0, 99) for i in range(1000)]

debut = process_time()
L.sort()
fin = process_time()
print(fin-debut)

##18
'''
On a deux boucles imbriquées qui font chacune len(L) itérations, donc O(len(L)^2).
'''