Les attendus
- Écrire un algorithme de tri
- Décrire un invaraint de boucle qui prouve la correction des tris par insertion, par sélection.
Introduction aux Tris
Mais qu'est-ce qu'un algorithme ?
Pourquoi étudier des algorithmes de tri ?
Autant ne pas le cacher, ces algorithmes sont déjà implémentés (quelque soit le langage) dans des fonctions très performantes.
En Python, on utilise la fonction sort() :
Le meilleur de nos futurs algorithmes de tri sera moins efficace que celui de cette fonction sort()…
Malgré cela, il est essentiel de se confronter à l’élaboration manuelle d’un algorithme de tri.
Le tri par sélection est le premier des deux algorithmes de tri que nous allons étudier (nous étudierons aussi le tri par insertion).
Ces deux algorithmes ont pour particularité de :
- ne pas nécessiter la création d’une nouvelle liste. Ils modifient la liste à trier en place.
- ne pas faire intervenir de fonctions complexes (comme la recherche d’un minimum par exemple)
Le cours
Algorithmes sur les tableaux
Lorsqu’on dispose de plusieurs données similaires (notes à un devoirs, dépenses journalières etc.) il est commode de les ranger dans
un tableau.
On est alors amené à effectuer de nombreuses opérations sur ces tableaux.
notes = [20,12,14,15,3]
Est-ce qu’un élève a eu 20 ?
La réponse est oui, 20 est le dernier élément du tableau. Pour une machine, répondre à cette question n’est pas immédiat.
En pratique, la seule manière qu’elle ait de répondre est de parcourir le tableau entier et de comparer un par un les éléments avec 20.
C’est ce qu’on appelle un parcours séquentiel.
Outils natifs de Python
IN avec une liste
Python propose l’instruction in qui teste l’appartenance :
>>>20 in tableau ==> True
>>>2 in tableau ==> False
Mais comment fait-il ?
3 in [1, 2, 3, 4] >>>>est équivalent à :
for element in [1, 2, 3, 4]:
if element == 3:
return True
return False
Il fait bien un parcours séquentiel !!!
Pour calculer une Moyenne
Pour calculer la moyenne à ce devoir, on pourrait utiliser :
moyenne = sum(tableau) / len(tableau)
Le danger des outils natifs, c’est que de telles instructions n’existent pas dans tous les langages !
L’algorithmie sur les tableaux
L’algorithmie sur les tableaux, c’est l’art de décrire une suite d’étapes précises pour parcourir, lire, modifier ou analyser les éléments d’un tableau un par un afin d’obtenir un résultat.
Les actions fondamentales (les 4 piliers)
Avec un tableau, un algorithme sert souvent à :
Parcourir
→ regarder chaque case du tableauChercher
→ trouver une valeur ou sa positionModifier
→ changer certaines valeursCalculer
→ somme, maximum, moyenne, comptage…
1 Le parcours d'un tableau
Cela demande forcement une boucle.Rappelons qu’il existe deux types de boucles : for et while ou bornée et non bornée.
Recherche d'un élément
Si « element » est dans le tableau : for x in T convient.
L’algorithme produit un booléen on ne s’intéresse donc pas aux indices
Algorithme :
contient (tableau T, objet x) -> booléen:
Pour chaque élément e de T,
Si e = x, alors on retourne Vrai
Si la boucle se termine, on retourne Faux
ATTENTION remarquez bien la position de la condition… on ne renvoie Faux que si la boucle se termine.
Recherche l'indice d'une cle
On dispose d’un tableau et d’une clé. On veut connaître l’indice de la clé dans le tableau. On répond -1 si la clé n’est pas présente.
Cette fois il faut l’indice : for i in range(len(T))
element =tab[i]
if element== cle:
return i
return -1
Notez la position de return -1. Il est au même niveau d’indentation que for ....
En effet, il faut attendre d’avoir parcouru tous les éléments pour savoir si la clé est présente ou non.
Recherche du maximum
Recherche l'indice du maximum
Modifier un tableau
Renverser un tableau
- On crée un tableau vide
Rpour nos éléments renversés - On parcourt le tableau
T,- pour chaque élément rencontré, on l’insère au début de R
- On renvoie
R
Calculer une moyenne
