Le tri par insertion
Comment ranges-tu des cartes à jouer dans ta main ? Tu les prends une par une, et tu glisses chacune à sa place parmi celles que tu tiens déjà. Cette méthode toute naturelle est un algorithme célèbre : le tri par insertion.
L'idée
On avance dans le tableau de gauche à droite. À chaque étape :
- on prend la valeur suivante ;
- on décale vers la droite toutes les valeurs plus grandes qu'elle, déjà triées ;
- on la pose dans le trou ainsi libéré.
La partie gauche du tableau est donc toujours triée, et elle grandit d'une case à chaque étape.
Avec [7, 3, 9, 2, 5] :
- on prend 3 : le 7 se décale, on pose 3 →
[3, 7, 9, 2, 5] ; - on prend 9 : rien n'est plus grand, il reste là →
[3, 7, 9, 2, 5] ; - on prend 2 : 9, 7 et 3 se décalent →
[2, 3, 7, 9, 5] ; - on prend 5 : 9 et 7 se décalent →
[2, 3, 5, 7, 9].
Le programme
cartes est un tableau vaut [7, 3, 9, 2, 5]
enMain est un nombre
j est un nombre
pour i de 1 à longueur(cartes) - 1
enMain vaut cartes[i]
j vaut i - 1
tant que j >= 0
si cartes[j] <= enMain alors
arrête
fin si
cartes[j + 1] vaut cartes[j]
j soustrait 1
fin tant que
cartes[j + 1] vaut enMain
affiche 'Étape ' + i + ' : ' + joindre(cartes, ' ')
fin pour
enMain garde la valeur qu'on est en train de placer.j recule dans la partie triée, tant qu'il trouve des valeurs plus grandes.cartes[j + 1] vaut cartes[j] décale une valeur d'une case vers la droite.- Quand la boucle s'arrête, la bonne place est
j + 1.
La boucle pour commence à 1 : une seule carte (celle de l'index 0) est déjà « triée ».
Question : La partie triée est [2, 5, 8] et on doit insérer 4. Combien de valeurs sont décalées ? — Deux. 8 et 5 sont plus grands que 4 : ils se décalent tous les deux. Le 2 ne bouge pas, et 4 se pose entre 2 et 5.
Pourquoi ce `si ... arrête` ?
On pourrait vouloir écrire tant que j >= 0 et cartes[j] > enMain. Mais attention : CoddyRun évalue les deux côtés d'un et. Quand j vaut -1, il essaierait de lire cartes[-1], et le programme s'arrêterait sur une erreur d'index.
Quand un test protège un accès à un tableau, on sépare les deux : la boucle vérifie l'index, puis un si à l'intérieur lit la case.
En procédure
Un tableau passé à une procédure est modifié directement : pas besoin de retourne.
procédure triInsertion(liste)
enMain est un nombre
j est un nombre
pour i de 1 à longueur(liste) - 1
enMain vaut liste[i]
j vaut i - 1
tant que j >= 0
si liste[j] <= enMain alors
arrête
fin si
liste[j + 1] vaut liste[j]
j soustrait 1
fin tant que
liste[j + 1] vaut enMain
fin pour
fin procédure
points est un tableau vaut [45, 12, 78, 30, 51]
appelle triInsertion(points)
affiche joindre(points, ' - ') // 12 - 30 - 45 - 51 - 78
Garder un tableau toujours trié
Le tri par insertion a un grand avantage : il sait ajouter une valeur dans un tableau déjà trié, sans tout recommencer. Idéal pour un classement qui se remplit au fil du jeu :
procédure insererTrie(liste, nouveau)
liste ajoute nouveau
k est un nombre vaut longueur(liste) - 1
tant que k > 0
si liste[k - 1] <= nouveau alors
arrête
fin si
liste[k] vaut liste[k - 1]
k soustrait 1
fin tant que
liste[k] vaut nouveau
fin procédure
classement est un tableau
appelle insererTrie(classement, 50)
appelle insererTrie(classement, 20)
appelle insererTrie(classement, 80)
appelle insererTrie(classement, 35)
affiche joindre(classement, ', ') // 20, 35, 50, 80
La nouvelle valeur est ajoutée au bout, puis elle « remonte » jusqu'à sa place.
Insertion ou bulles ?
- Sur un tableau presque trié, le tri par insertion est très rapide : chaque valeur est déjà à sa place ou tout près, il n'y a presque rien à décaler.
- Sur un tableau à l'envers, c'est son pire cas : chaque valeur doit traverser toute la partie triée.
- Comme le tri à bulles, il devient lent sur de très grands tableaux : pour 1000 valeurs en désordre, il faut de l'ordre de 250 000 décalages.
Dans tes programmes, trier(tableau) fait le travail. Mais tu sais maintenant comment on peut s'y prendre... et tu ne rangeras plus tes cartes de la même façon !
En résumé
- Le tri par insertion prend chaque valeur et la glisse à sa place dans la partie déjà triée.
- Les valeurs plus grandes sont décalées d'une case vers la droite.
- CoddyRun évalue les deux côtés d'un
et : on protège l'accès au tableau avec un si séparé. - Il est très efficace sur un tableau presque trié, et pour insérer une valeur dans un tableau trié.
