Programme pour l'exercice 4 de la série 4

s04e04.py

from typing import List
from time import time
from random import randint

def insertion_sort(l: List[int]) -> List[int]:
    """
    Implémentation du tri par insertion.
    :param l: Une liste de départ
    :return:  La liste triée
    """
    i: int = 1
    while i < len(l):
        j: int = i
        while j > 0 and l[j] < l[j - 1]:
            temp = l[j - 1]
            l[j - 1] = l[j]
            l[j] = temp
            j -= 1
        i += 1
    return l


def fusion_sort(l: List[int]) -> List[int]:
    """
    Implémentation du tri fusion
    :param l: Une liste de départ
    :return:  La liste triée
    """
    if len(l) == 1:
        return l
    m: int = len(l) // 2
    l1: List[int] = fusion_sort(l[:m])
    l2: List[int] = fusion_sort(l[m:])
    return fusion(l1, l2)

def fusion(l1: List[int], l2: List[int]) -> List[int]:
    """
    Implémentation de la fusion de deux listes
    :param l1: La première liste à fusionner
    :param l2: La seconde liste à fusionner
    :return:   Une liste triée qui fusionne l1 et l2
    """
    j1: int = 0
    j2: int = 0
    fusion_list: List[int] = []
    while j1 < len(l1) and j2 < len(l2):
        if l1[j1] <= l2[j2]:
            fusion_list.append(l1[j1])
            j1 += 1
        else:
            fusion_list.append(l2[j2])
            j2 += 1
    if j1 == len(l1):
        fusion_list += l2[j2:]
    else:
        fusion_list += l1[j1:]
    return fusion_list


def create_random_list(size: int) -> List[int]:
    """
    Générateur de liste au contenu aléatoire.
    :param size: La taille de la liste
    :return:     Une liste aléatoire de taille size
    """
    l: List[int] = []
    for i in range(size):
        l.append(randint(0, 3*size))
    return l


# Nombre d'essais
trials: int = 20

# Deux listes pour récupérer le temps d'exécution à chaque tri
time_insertion_sort: List[float] = []
time_fusion_sort: List[float] = []

for i in range(trials):
    print(f"Trial number: {i}")
    # Génération aléatoire d'une liste de taille 12000
    # Cette liste est copiée pour que le tri par insertion et le tri fusion
    # s'exécute sur une même liste initiale
    insertion_list = create_random_list(12000)
    fusion_list = insertion_list.copy()

    # Réalisation du tri par insertion, avec calcul du temps écoulé entre le début 
    # et la fin de l'exécution
    print("Working on insertion sort...")
    start_time: float = time()
    insertion_sort(insertion_list)
    stop_time: float = time()
    time_insertion_sort.append(stop_time - start_time)
    print("Insertion sort done...")

    # Réalisation du tri fusion, avec calcul du temps écoulé entre le début 
    # et la fin de l'exécution
    print("Working on fusion sort...")
    start_time = time()
    fusion_sort(fusion_list)
    stop_time = time()
    time_fusion_sort.append(stop_time - start_time)
    print("Fusion sort done...")

# Affichage de la moyenne, du min, et du max du temps d'exécution pour les deux tris.
print(f"Temps moyen pris pour la tri par insertion: {(sum(time_insertion_sort) / trials):2f} secondes.")
print(f"Le minimum atteint par le tri par insertion est de : {(min(time_insertion_sort)):2f} secondes.")
print(f"Le maximum atteint par le tri par insertion est de : {(max(time_insertion_sort)):2f} secondes.")

print(f"Temps moyen pris pour la tri fusion: {(sum(time_fusion_sort) / trials):2f} secondes.")
print(f"Le minimum atteint par le tri fusion est de : {(min(time_fusion_sort)):2f} secondes.")
print(f"Le maximum atteint par le tri fusion est de : {(max(time_fusion_sort)):2f} secondes.")