import random
from time import time

# =============================================
# Exercice 1 : Création des listes de test
# =============================================

# 1. Listes inversées (triées à l'envers)
L10 = []
for i in range(9, -1, -1):      # de 9 à 0
    L10.append(i)

L1000 = []
for i in range(999, -1, -1):
    L1000.append(i)

L10000 = []
for i in range(9999, -1, -1):
    L10000.append(i)

print("Listes inversées créées : L10, L1000, L10000")


# 2. Fonction pour générer une liste aléatoire
def gen_liste(n, N):
    """Renvoie une liste de n entiers aléatoires entre 0 et N-1 inclus"""
    L = []
    for i in range(n):
        L.append(random.randint(0, N-1))
    return L


# 3. Listes aléatoires
A10 = gen_liste(10, 10)
A1000 = gen_liste(1000, 1000)
A10000 = gen_liste(10000, 10000)

print("Listes aléatoires créées : A10, A1000, A10000")


# =============================================
# Exercice 2 : Fonction d'échange
# =============================================

def echange(L, i, j):
    """Échange les éléments L[i] et L[j] en une seule ligne"""
    L[i], L[j] = L[j], L[i]   # c'est tout !
    # return None  (pas besoin de return)


# =============================================
# Exercice 3 : Tri par sélection
# =============================================

def select(L):
    """Tri par sélection (en place)"""
    n = len(L)
    
    for i in range(n):                  # pour chaque position i
        # On cherche le minimum dans L[i..n-1]
        indice_min = i
        for j in range(i+1, n):
            if L[j] < L[indice_min]:
                indice_min = j
        
        # On échange avec la position i
        echange(L, i, indice_min)


# Test
L_test = [5, 2, 9, 1, 6]
select(L_test)
print("Exemple tri par sélection :", L_test)


# =============================================
# Exercice 4 : Tri par insertion
# =============================================

def insere(L):
    """Tri par insertion (en place)"""
    n = len(L)
    
    for i in range(1, n):           # on commence à 1 car le premier est déjà "trié"
        j = i
        while j > 0 and L[j] < L[j-1]:
            echange(L, j, j-1)
            j = j - 1


# Test
L_test = [5, 2, 9, 1, 6]
insere(L_test)
print("Exemple tri par insertion :", L_test)


# =============================================
# Exercice 5 : Tri à bulles
# =============================================

def tribulles(L):
    """Tri à bulles (en place)"""
    n = len(L)
    
    for i in range(n):                    # nombre de passes
        for j in range(0, n-1-i):         # on réduit la zone à trier
            if L[j] > L[j+1]:
                echange(L, j, j+1)


# Fonction qui compte le nombre d'échanges (pour vérification)
def echanges_bulles(L):
    """Trie une COPIE de L et renvoie le nombre d'échanges effectués"""
    M = L[:]      # on travaille sur une copie
    n = len(M)
    compteur = 0
    
    for i in range(n):
        for j in range(0, n-1-i):
            if M[j] > M[j+1]:
                echange(M, j, j+1)
                compteur = compteur + 1
    return compteur


# Fonction qui compte les inversions
def compte_inversions(L):
    """Compte le nombre d'inversions dans la liste"""
    compteur = 0
    n = len(L)
    for i in range(n):
        for j in range(i+1, n):
            if L[i] > L[j]:
                compteur = compteur + 1
    return compteur


# =============================================
# Exercice 6 : Tri rapide (Quicksort)
# =============================================

def Separation(L, k):
    """Renvoie trois listes : < k, == k, > k"""
    L1 = []   # éléments < k
    L2 = []   # éléments == k
    L3 = []   # éléments > k
    
    for x in L:
        if x < k:
            L1.append(x)
        elif x == k:
            L2.append(x)
        else:
            L3.append(x)
    
    return L1, L2, L3


def quicksort(L):
    """Tri rapide (version récursive qui renvoie une nouvelle liste)"""
    n = len(L)
    if n <= 1:
        return L                    # cas de base
    
    # On prend le premier élément comme pivot
    pivot = L[0]
    L1, L2, L3 = Separation(L, pivot)
    
    # Appel récursif
    return quicksort(L1) + L2 + quicksort(L3)


# =============================================
# Tests et mesures de temps
# =============================================

print("\n=== Tests et mesures de temps ===")

# On fait des copies pour ne pas modifier les listes originales
L1000_copy = L1000[:]
A1000_copy = A1000[:]

t1 = time()
select(L1000_copy)
print("Temps tri par sélection sur L1000 (inversée) :", round(time()-t1, 4), "s")

t1 = time()
insere(A1000_copy)
print("Temps tri par insertion sur A1000 (aléatoire) :", round(time()-t1, 4), "s")

t1 = time()
tribulles(L1000[:])
print("Temps tri à bulles sur L1000 :", round(time()-t1, 4), "s")

t1 = time()
quicksort(A1000[:])
print("Temps tri rapide sur A1000 :", round(time()-t1, 4), "s")


# Test inversions = échanges bulles
test_inv = [5, 3, 8, 1, 4]
print("\nNombre d'inversions dans", test_inv, ":", compte_inversions(test_inv))
print("Nombre d'échanges bulles :", echanges_bulles(test_inv))