Tri par comptage d'une liste d'entier

1. 1

   Indice

   Initialiser une variable avec le premier élément puis parcourir le reste de la liste pour mettre à jour la valeur maximale.
   Écrire une fonction vmax(L: list[int]) -> int | None qui renvoie l'entier maximal de la liste L, ou None si la liste est vide. Par exemple vmax([3, 1, 4, 1, 5]) renvoie 5.
   flowchart TD Start([Début : Liste L]) --> Cond_Empty{"len(L) == 0 ?"} Cond_Empty -->|Vrai| EndNone([Fin : Retourner None]) Cond_Empty -->|Faux| Init["max_val = L[0]
   i = 1"] Init --> Cond_Loop{"i < len(L) ?"} Cond_Loop -->|Faux| EndMax([Fin : Retourner max_val]) Cond_Loop -->|Vrai| Cond_Compare{"L[i] > max_val ?"} Cond_Compare -->|Vrai| Update["max_val = L[i]"] Cond_Compare -->|Faux| Inc_i["i = i + 1"] Update --> Inc_i Inc_i --> Cond_Loop
2. 2

   Indice

   Dimensionner un tableau de zéros selon la valeur maximale puis incrémenter l'indice correspondant à chaque élément.
   Écrire une fonction occurrences(L: list[int]) -> list[int] qui renvoie le tableau des occurrences des entiers de la liste L. Par exemple occurrences([1, 2, 2, 3]) renvoie [0, 1, 2, 1].
   flowchart TD Start(["Début : Liste L"]) --> Cond*Empty{"len(L) == 0 ?"} Cond_Empty -->|Vrai| EndEmpty(["Fin : Retourner []"]) Cond_Empty -->|Faux| Call_Vmax["Appeler la fonction :
   max_val = vmax(L)"] Call_Vmax --> Init_Occ["Créer le tableau de compteurs
   occ = [0 for * in range(max_val + 1)]
   i = 0"] Init_Occ --> Cond_Loop{"i < len(L) ?"} Cond_Loop -->|Faux| EndOcc(["Fin : Retourner occ"]) Cond_Loop -->|Vrai| Count["Incrémenter la case correspondante
   occ[L[i]] = occ[L[i]] + 1"] Count --> Inc_i["i = i + 1"] Inc_i --> Cond_Loop
3. 3

   Indice

   Parcourir le tableau des occurrences pour reconstruire progressivement la liste triée en ajoutant chaque valeur selon son compteur.
   Écrire une fonction tri_comptage(L: list[int]) -> list[int] qui renvoie une nouvelle liste triée par ordre croissant en utilisant le tri par dénombrement. Par exemple tri_comptage([3, 1, 4, 1, 5]) renvoie [1, 1, 3, 4, 5].
   flowchart TD Start([Début : Liste L]) --> Cond_Empty{"len(L) == 0 ?"} Cond_Empty -->|Vrai| EndEmpty(["Fin : Retourner []"]) Cond_Empty -->|Faux| Call_Occ["Appeler la fonction :
   occ = occurrences(L)"] Call_Occ --> Init_Sort["Initialiser la structure de tri
   sorted_lst = []
   i = 0"] Init_Sort --> Cond_Loop_i{"i < len(occ) ?"} Cond_Loop_i -->|Faux| EndSort(["Fin : Retourner sorted_lst"]) Cond_Loop_i -->|Vrai| Cond_While{"occ[i] > 0 ?"} Cond_While -->|Vrai| Append["Ajouter la valeur à la liste triée
   sorted_lst.append(i)
   occ[i] = occ[i] - 1"] Append --> Cond_While Cond_While -->|Faux| Inc_i["i = i + 1"] Inc_i --> Cond_Loop_i