"""
Thème 10 --- Méthodes de tri (2025-26)

Il y a trois méthodes de tri à connaître :

1. Tri à bulles
2. Tri insertion
3. Tri récursif

 - Jamais tombé à l'écrit
 - Une planche d'info l'utilise à l'oral.

Vous DEVEZ, pour ne pas vous faire avoir :
- être capable d'expliquer le principe des trois méthodes
- être capable d'en programmer une tous seuls.
- savoir au moins trier artisanalement en désespoir de cause ( =  méthodes de secours) : p.ex avec la méthode du II 2a) ou 2b).

- Je pense que le tri à bulles est le plus simple à
retenir et expliquer. Question de goût.

- Si vous partez sur 3., vous risquez d'avoir des questions
sur la récursivité.

- Tout est résumé sur la fiche SPE16.

"""
## Importations utiles
import random as rd

## Constantes

N = 1000 # longueur maximale des listes et
         # et des coeffs s'y trouvant

## Préliminaires sur les effets de bord

def touchepas(L):
    M = L[:]
    M[0]=-15
    return M

def touche(L):
    L[0]=-15  # fait remarquable : pas de return

# effet indésirable de la fonction touche : elle modifie
# l'objet L ; si l'utilisateur ne le sait pas (et
# la seule façon de le savoir est de lire la doc),
# son programme risque de ne pas produire les résultats
# attendus.

# Ces effets indésirables (en anglais : side effects)
# peuvent néanmoins être utilisés à  notre avantage, SI L'ON
# EST CONSCIENT DE LEUR EXISTENCE. La terminologie
# française est : "effets de bord" (peut-être pour
# dépouiller l'expression d'origine de toute connotation
# négative).

# VOUS DEVEZ CONNAITRE CETTE NOTION : elle s'applique
# aux objets structurés mutables.


## II Méthodes de secours

## II A a) Méthode artisanale et assez intuitve.

def pos_min(L):
    n = len(L)
    j = 0                   # initialisation de la position du
                            # minimum temporaire.
    m = L[j]                # valeur du minimum temporaire.
    for k in range(n):      # je parcours L.
        if L[k]<m:          # dès que je croise un elem < m,
            j,m = k,L[k]    # cet elem devient le nouveau min
                            # et je mémorise sa position
    return j                # à la fin du parcours, j est
                            # la position du min de L


def test(n):
    """
    renvoie une liste de n termes de {0...n-1} tirés
    au hasard (répétitions autorisées). Utile pour
    tester nos fonctions sur des listes
    """
    return [ rd.randrange(n) for _ in range(n)]


def tri_basique(L):
    M = L[:]    # copie de la liste L que je vais vider
    Ltriee = []
    while len(M)>0:   # tant qu'il y a des elem dans M :
        j = pos_min(M) # je cherche son plus petit elemt,
        Ltriee.append(M[j]) # je le mets dans Ltriee,
        M.pop(j)            # je l'enlève de M, et je
                            # recommence.
    return Ltriee

## II B) méthode artisanale (vient d'un oral de G2E)

## Q1) a.

def multi(a,L):
    La = [x for x in L if x==a ] # sous-liste de tous
                                 # les a contenus dans L
    return len(La) # donne le nombre de a dans L

def tri_bis(L):
    Ltriee=[]
    for a in range(N):
        Ltriee+=multi(a,L)*[a] # concaténations et
                               # et réplications
                               # successives
    return Ltriee

# Remarque : multi(a,L)*[a] est la liste La elle-même !
#            on aurait pu se passer de la fonction
#            multi(a,L), mais la question était posée
#            ainsi à G2E.

## III Tri à bulles (bubblesort)

## Q2.

def permute(L,i,j):
    """
    version sans effets de bord
    """
    M =  L[:]  # copie de L pour ne pas la modifier
    M[i],M[j] = M[j],M[i]   # je permute dans M
    return M

## Q3
def bubblesort(L):
    """
    version sans effets de bord.
    Au premier parcours, il y a n-1 comparaisons de paires
    Au (n-1)-ème  parcours,on a fini.
    """
    M =  L[:]  # copie de L pour ne pas la modifier
    n = len(M)
    # Boucle des n-1 parcours successifs.
    for k in range(1,n):     # premier parcours : n-1
                             # comparaisons de paires
        for i in range(n-k): # examen des n-k   paires
                             # du parcours numéro k
            if M[i]>M[i+1]:
                M = permute(M,i,i+1)
    return M

## Q4
def bubblesort(L):
    """
    version exploitant les effets de bord
    """
    n = len(L)
    for k in range(1,n):
        for i in range(n-k):
            if L[i]>L[i+1]:
                L[i],L[i+1] = L[i+1],L[i]

### IV Tri insertion

# C'est la méthode employée pour trier les cartes de sa main


##Q5

def retrograde(L,i):
    # utilise une boucle while.
    # On exprime la condition de sortie :
    # L[i] est bien placé si { i = 0 ou L[i-1]<L[i] }
    # la négation de cette condition me dit quoi mettre
    # dans le while :
    """
    version sans effets de bord
    """
    M =  L[:]  # copie de L pour ne pas la modifier
    i2 = i # j'initialise la valeur de la position finale
    while  i2>0 and  M[i2-1]>=M[i2]:
        M[i2],M[i2-1] = M[i2-1],M[i2] # la retrogradation
        i2-=1                         # consiste en des
    return M                          # permutations
                                      # successives

def tri_insertion(L):
    M =  L[:]  # copie de L pour ne pas la modifier
    n = len(M)
    for k in range(n-1):
        pivot = M[k]
        if M[k+1]< pivot:
            M = retrograde(M,k+1)
    return M

##Q6 Version effets de bord du tri insertion

def retrograde(M,i):
    i2 = i
    while   M[i2-1]>=M[i2] and i2>0:
        M[i2],M[i2-1] = M[i2-1],M[i2]
        i2-=1

def tri_insertion(M):
    n = len(M)
    for k in range(n-1):
        pivot = M[k]
        if M[k+1]< pivot:
            retrograde(M,k+1)


## V Tri récursif

def quicksort(L):
    n = len(L)
    if n<=1:
        return L
    else:
        pivot=L[0]
        left,right=[],[]
        for i in range(1,n):
            if L[i]>pivot:
                right+=[L[i]]
            else:
                left+=[L[i]]
        return quicksort(left)+[pivot]+quicksort(right)