Fiche de révision : Algorithmes sur les tableaux

Parcours séquentiel de liste

• Le parcours séquentiel donne un accès individuel aux éléments d’une structure donnée, en les parcourant un par un et dans l’ordre.
• Le parcours séquentiel d’une liste s’effectue avec une boucle de type for … in .

Recherche d’occurrence(s)

• La recherche d’occurrence, dans une liste non triée, s’effectue en comparant chaque élément de la liste à l’élément recherché, jusqu’à le trouver ou jusqu’à atteindre la fin de la liste.
• La recherche d’occurrence fonctionne aussi avec des types de données tels que :
• une liste de nombres ;
• des chaînes de caractères ;
• des booléens ;
• un tuple de tuples.
• Si l’on veut rechercher toutes les occurrences, il faut parcourir l’intégralité de la liste.

Recherche d’extremums

• Nous pouvons retourner simultanément le minimum et le maximum d’une liste d’éléments.
• Si les listes ne sont pas triées, la recherche d’extremums nous oblige à les parcourir en totalité.
• La recherche d’extremums fonctionne aussi avec des types de données tels que :
• une liste de nombres ;
• des chaînes de caractères ;
• des booléens ;
• un tuple de tuples.

Calcul de moyenne

• Le calcul de la moyenne est assez proche de la recherche d’extremums, et nous oblige à nouveau à parcourir l’intégralité des éléments de la liste.
• Mais il n’est pas possible de calculer la moyenne d’une liste de chaines de caractères, cette notion mathématique n’ayant pas de sens pour ce type de donnée.

Coût algorithmique

• Pour un nombre $n$ d’éléments dans la liste, on parcourt au plus $n$ éléments.
• Le coût algorithmique des recherches séquentielles est linéaire, de l’ordre de $n$, noté $\text{O}(n)$.

Tri par sélection

Principe du tri par sélection

• Le tri par sélection repose sur des comparaisons et des échanges de positions dans la liste.
• À l’issue du traitement, la liste est entièrement triée.

Implémentation

L’implémentation du tri par sélection repose sur l’imbrication de deux boucles :

• la boucle extérieure parcourt la liste séquentiellement ;
• la boucle intérieure parcourt la portion de liste restante pour en déterminer le minimum.

Terminaison et complexité

• L’algorithme est composé de deux boucles for … in imbriquées.
• Chacune de ces boucles se terminera car les itérations de type for ou for … in ne peuvent pas produire de boucles infinies.
• Les boucles étant imbriquées le coût est quadratique. La complexité du tri par sélection est $\text{O}(n^{2})$.

Tri par insertion

Principe du tri par insertion

• Le principe du tri par insertion est analogue à celui du tri d’un jeu de cartes. Cette méthode assez intuitive permet de trier simplement et rapidement, un paquet de cartes par exemple.

Terminaison et complexité

• L’algorithme est composé de deux boucles imbriquées :
• la boucle externe for … in se terminera à l’épuisement des éléments de la liste ;
• dans la boucle interne de type while, la variable j est un variant de boucle décroissant à chaque tour jusqu’à devenir nul.
• Le coût est quadratique, la complexité temporelle de l’algorithme de tri par insertion est $\text{O}(n^{2})$.
• La performance du tri par sélection est meilleure quand les données sont presque triées ou quand le nombre de données à trier reste modéré.
• Pour la recherche dichotomique le coût est réduit mais requiert en entrée une liste ordonnée.