ICC 23-24 : Série 4 – Correction

s04-correction.py

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

'''
Exercice 1: Création et parcours de liste
a) On peut utiliser la méthode append() pour ajouter l'élément d'indice 0, puis celui d'indice 1 ;
ou extend() pour ajouter les deux éléments d'un coup.
Ensuite, on peut profiter de la fonction range(start, stop) pour commencer à la valeur 2, et s'arrêter à 9.
'''
x: int = 10
fibo: List[int] = []
fibo.extend([0, 1])
for i in range(2, 10):
    fibo.append(fibo[i-1] + fibo[i-2])

'''b) La fonction print() utilisée sur une liste affiche toutes ses valeurs.'''
print(fibo)

'''c) Rien à signaler de nouveau ici.'''
for element in fibo:
    print(element)

'''d) Rien à signaler de nouveau ici.'''
for index, element in enumerate(fibo):
    print(f"F({index}) = {element}")



'''
Exercice 2: Code tracing – for et while
Le programme donné contient une erreur parce que :
- range(len(numbers)) est évalué une seule fois, en tout début de boucle
- La taille de la liste diminue au fur et à mesure que nous supprimons des éléments
- Il arrive un moment où nous cherchons à accéder à numbers[index] pour une valeur de index > len(numbers).
  D'où l'erreur "IndexError: list index out of range"

Pour corriger ce problème, il est possible d'utiliser une boucle while à la place.
La différence principale est que la condition de la boucle while est évaluée à chaque itération. Et donc,
bien que la taille de la liste peut diminuer à chaque itération, cette taille est recalculée à chaque fois
que l'on détermine s'il faut répéter encore une fois les instructions.
'''
numbers: List[int] = [1, 1, 1, 3, 5, 5]

# for index in range(len(numbers)):
#     while numbers.count(numbers[index]) > 1:
#         numbers.remove(numbers[index])
# print(numbers)

index: int = 0
while index < len(numbers):
    while numbers.count(numbers[index]) > 1:
        numbers.remove(numbers[index])
    index += 1
print(numbers)


'''
Exercice 3: Recherche de doublons dans une liste
a) Il y a une approche naïve, qui consiste à évaluer toutes les paires d'éléments dans la liste.
Ou il y a une approche plus "intelligente", qui consiste à trier d'abord la liste.
Ou on peut s'appuyer sur ce qui est déjà donné en exercice 1 avec la méthode count().
'''

def naive_has_duplicates(l: List[int]) -> bool:
    n = len(l)
    for i in range(n-1):
        for j in range(i + 1, n):
            if l[i] == l[j]:
                return True
    return False

def has_duplicates(l: List[int]) -> bool:
    n = len(l)
    l.sort()
    for i in range(n-1):
        if l[i] == l[i+1]:
            return True
    return False


print(naive_has_duplicates([]))                     # False
print(naive_has_duplicates([9, 3, 2, 5, 1]))        # False
print(naive_has_duplicates([1, 1]))                 # True
print(naive_has_duplicates([1, 2, 2, 3, 1, 5, 1]))  # True
# print(has_duplicates([]))                           # False
# print(has_duplicates([9, 3, 2, 5, 1]))              # False
# print(has_duplicates([1, 1]))                       # True
# print(has_duplicates([1, 2, 2, 3, 1, 5, 1]))        # True


'''
b) Même idée, il y a une approche naïve, une autre basée sur la liste triée, 
et une autre encore utilisant la méthode count().
'''

def naive_find_duplicates(l: List[int]) -> List[int]:
    n = len(l)
    duplicates: List[int] = []
    for i in range(n-1):
        for j in range(i+1, n):
            if l[i] == l[j] and l[i] not in duplicates:
                duplicates.append(l[i])
    return duplicates


def find_duplicates(l: List[int]) -> List[int]:
    n = len(l)
    l.sort()
    duplicates: List[int] = []
    index: int = 0
    while index < n - 1:
        if l[index] == l[index + 1] and l[index] not in duplicates:
            duplicates.append(l[index])
        index += 1
    return duplicates


print(naive_find_duplicates([]))                    # []
print(naive_find_duplicates([1, 2, 3, 5, 9]))       # []
print(naive_find_duplicates([1, 1]))                # [1]
print(naive_find_duplicates([1, 2, 2, 3, 1, 5, 1])) # [1, 2] ou [2, 1]

# print(find_duplicates([]))                    # []
# print(find_duplicates([1, 2, 3, 5, 9]))       # []
# print(find_duplicates([1, 1]))                # [1]
# print(find_duplicates([1, 2, 2, 3, 1, 5, 1])) # [1, 2] ou [2, 1]

'''
c) On peut se servir de la fonction find_duplicates() pour récupérer la liste des doublons.
Si la longueur de cette liste est supérieure strictement à zéro, alors c'est qu'il y a au moins un doublon.
'''

def new_has_duplicates(l: List[int]) -> bool:
    duplicates = find_duplicates(l)
    return len(duplicates) > 0


print(new_has_duplicates([]))                     # False
print(new_has_duplicates([9, 3, 2, 5, 1]))        # False
print(new_has_duplicates([1, 1]))                 # True
print(new_has_duplicates([1, 2, 2, 3, 1, 5, 1]))  # True


'''
Exercice 4: Algorithmes de tri, complexité temporelle
Dans cet "exercice", nous avons défini des fonctions permettant de réaliser
les algorithmes de tri par insertion et de tri fusion.
Dans le pire cas, le tri par insertion a une complexité en n^2 tandis que 
le tri fusion a une complexité en nlog(n).
Nous allons voir combien de temps ces algorithmes prennent en moyenne pour 
trier des grands jeux de données.
'''

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.")


'''
Exercice 5: Tri par sélection
a) Création de la liste de taille 20, avec des valeurs aléatoires
'''
ints: List[int] = []
for i in range(20):
    ints.append(randint(0, 100))

'''
b) et c) Recherche, dans la liste complète, du minimum après l'indice start_index
L'utilisation d'une boucle while est peut-être plus simple ici, puisque la variable index
peut directement prendre les bonnes valeurs d'indices (ce qui est moins direct avec une boucle for)
'''
def find_min_index(l: List[int], start_index: int = 0) -> int:
    min_value = l[start_index]
    min_index = start_index
    index: int = start_index
    while index < len(l):
        if l[index] < min_value:
            min_value = l[index]
            min_index = index
        index += 1
    return min_index

'''
d) Pour effectuer un tri par sélection, on cherche les minimums successifs, d'où 
la présence de la boucle. À noter que les bornes de cette boucle pourraient être 
réduites pour éviter des itérations inutiles.
'''
def selection_sort(l: List[int]) -> None:
    for i in range(len(l)):
        min_index = find_min_index(l, start_index=i)
        tmp = l[i]
        l[i] = l[min_index]
        l[min_index] = tmp

print(find_min_index([3, 1, 4, 1, 18])) # 1 
print(find_min_index([3, 1, 4, 1, 18], 0)) # 1, équivalent 
print(find_min_index([3, 1, 4, 1, 18], start_index=2)) # 3 
print(find_min_index([3, 1, 4, 1, 18], start_index=4)) # 4

print(ints)
selection_sort(ints)
print(ints)