Algorithmes sur les tableaux
Parcours séquentiel de liste
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 .
Recherche d’occurrence(s)
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
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
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
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
Tri par sélection
Principe du 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
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é
Terminaison et complexité
- L’algorithme est composé de deux boucles imbriquées.
- Chacune de ces boucles se terminera car les itérations de type ou 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
Tri par insertion
Principe du 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é
Terminaison et complexité
- L’algorithme est composé de deux boucles imbriquées :
- la boucle externese terminera à l’épuisement des éléments de la liste ;
- dans la boucle interne de type, la variable 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.