Tri par insertion, par sélection
Algorithmique
Plan
Terminaison d'un algorithme
De nombreux algorithmes contiennent des boucles non bornées (boucles tant que), ou de la récursivité (vu en terminale). Ces méthodes peuvent provoquer des boucles infinies. S'assurer qu'un algorithme va s'arrêter quelles que soient les données est primordial et s'appelle vérifier la terminaison d'un algorithme. Attention vérifier la terminaison ne signifie pas vérifier la correction de l'algorithme (la validité) qui consiste à vérifier que l'on aura le résultat attendu.
Voici un exemple simple de boucle infinie:
## exemple 1:
➦ gagne=False
➦ tant que pas gagne
➦ affiche 'boucle infinie'
## exemple 2: tentative d'afficher les nombres impairs jusque 10
➦ initialiser i à 1
➦ tant que i pas égal à 10
➦ afficher i
➦ incrémenter i de 2
Parmi les oublis très fréquents: un compteur que l'on doit incrémenter en fin de boucle! Pour qu'une boucle ne soit pas infinie, il faut que les variables qui sont dans les conditions soient modifiées à un moment ou un autre et puissent prendre la valeur d'arrêt.
Invariant de boucle
Un invariant de boucle est une propriété qui est vraie pour tous les passages dans la boucle. L'invariant doit être vrai avant d'entrer dans la boucle (Initialisation) et rester vrai jusquà la fin de celle-ci (Conservation et Terminaison). Trouver et prouver que l'on a un invariant de boucle permet très généralement de prouver la terminaison et la correction (validité) d'un algorithme. On raisonne par récurrence, si on arrive à montrer que l'invariant est vrai à l'étape n induit qu'il est vrai à l'étape n+1 (conservation) et si l'on sait qu'il est vrai au départ alors on a la preuve.
Prenons l'exemple de la recherche du maximum vu sur cette page.
➦ intialiser maximum à l'élément 0 de la liste
➦ pour tous les éléments de la Liste à partir du 2nd
➦ si l'élément est plus grand que maximum
➦ mettre maximum à la valeur de élément
➦ afficher maximum
Dans cet exemple, l'invariant sera la propriété: "maximum à l'étape n est le maximum de la liste d'éléments de 0 à n".
(Initialisation) Ma propriété est vraie avant d'entrer dans la boucle puisque maximum vaut l'élément 0
Supposons que l'on a le maximum à l'étape n donc de la sous liste de 1 à n éléments et vérifions la conservation. Si le n+1 ème élément est plus grand que maximum alors cet élément devient le maximum de la sous liste de n+1 éléments et sinon on garde l'ancien maximum qui devient donc le maximum de la sous liste de n+1 éléments. La propriété est donc vraie à la n+1 ième étape si vraie à la n ième.
Comme la propriété est vraie au départ, elle est toujours vraie et donc lorsque l'on sort de la boucle on est assuré d'avoir le maximum. On a donc la terminaison.
Tri par insertion
On parle de tri lorsque l'on veut classer des données d'un tableau avec une relation d'ordre définie. Par exemple, ranger des nombres dans l'ordre croissant. Bien sûr vous trouverez une fonction dans votre langage capable de faire cela, mais il est indispensable de connaitre les principaux algorithmes qui mènent à cela. Pourquoi? Parce qu'un jour ou l'autre, vous aurez besoin de ranger autre chose que des nombres avec une relation d'ordre inconnue de votre langage.
Le principe du tri par insertion est assez naturel. On prend les cartes une par une en commençant par la première.
- Au départ la première est supposée à sa place. On regarde la deuxième et on compare à la premiere, on échange si besoin. Les deux premières cartes sont donc rangées dans l'ordre.
- On regarde la troisième, on compare aux précédentes en partant de la plus proche à la première et on échange si l'ordre n'est pas bon. Si l'on n'échange pas cela signifie que l'on peut passer à la carte suivante. Maintenant les 3 premières cartes sont rangées.
- On regarde la 4ème carte et on la fait ainsi descendre à la position qui lui correspond...les 4 premières cartes sont rangées.
- On poursuit ainsi jusque la dernière carte.
Voyons l'algorithme:
➦ on dispose d'une liste de nombre de longueur L
➦ pour i allant de 0 à L-1
➦ j=i
➦ tant que j>0 et liste[j-1]> liste[j]:
➦ echanger(liste[j-1], liste[j])
➦ décrémenter j
Trouver l'invariant de boucle et prouver la terminaison.
Prouver que la complexité dans le pire des cas est quadratique.
Tri par selection
Aussi simple que le précédent.
- On cherche le plus petit élément du tableau et on l'échange avec celui qui est au début. Le premier élément est maintenant le plus petit
- Maintenant on cherche le plus petit élément du tableau mais en partant du 2nd élément et on l'échange avec celui qui est placé deuxième. Les deux premiers éléments sont les plus petits et sont rangés.
- On poursuit ainsi.
Voici l'algorithme, je vais vous donner aussi une fonction qui donne le rang (l'index) de l'élément le plus petit d'une liste.
##fonction qui retourne le rang de l'element
##le plus petit du debut au dernier élément d'un tableau
➦ fonction mini avec paramètres 'liste' et index 'debut' de recherche
➦ initialiser mini à liste[debut]
➦ initialiser index_mini à debut
➦ pour i allant de debut à longueur_liste-1
➦ si mini>liste[i]
➦ mini reçoit liste[i]
➦ index_mini reçoit i
➦ retourner index_mini
➦
##fonction tri selection
➦ fonction tri_selection avec paramètre liste
➦ initialiser longueur_liste à la longueur de la Liste
➦ pour i allant de 0 à longueur_liste-1
➦ index_du_min reçoit mini(liste,i)
➦ echanger liste[i] et liste[index_du_min]
➦ retourner(liste)
Trouver l'invariant de boucle et prouver la terminaison.
Prouver que la complexité dans le pire des cas est quadratique.
Tri par selection
- Ecrire le programme de tri par insertion.
- Ecrirer le programme de tri par selection.
- Quel est le pire des cas pour chacun de ces algorithmes? Et le meilleur?
- Etablir la complexité du tri par insertion
Etablir la complexité du tri par selection
Les langages informatiques ont des fonctions qui effectuent le tri mais parfois on ne peut pas les utiliser! Prenons l'exemple d'une liste de coordonnées (x,y,z). On veut classer les points du plus bas (plus petit z) au plus haut. Adaptez vos programmes précédents pour qu'ils réalisent cette tâche.
