C'est un tri qualifié de lent.
Comprendre
Une illustration pour comprendre le principe de ce tri est d'aller sur le site de l'université de San Fransico pour visualiser le fonctionnement de l'algorithme :
- un premier index qui mémorise l'endroit jusqu'où les valeurs précédentes du tableau sont triés par ordre croissant,
- Pour chaque valeur de cet index, les opérations de tri ont pour objectif de faire remonter vers le début la valeur, étape par étape, de telle sorte que la valeur précédente est plus petite comme le montre le détail lorsque l'index vaut 3 :
VarB permet de remonter vers le début du tableau
Tab[ ] représente le tableau
A chaque étape j'ai indiqué la valeur de varA et varB et les opérations à réaliser.
Soit l'algorithme suivant :
varA ← 1
tant que varA <longueur(tab)
varB← varA - 1
k ← tab[varA]
tant que varB>=0 et que tab[varB]>k
tab[varB+1] ← tab[varB]
varB ← varB-1
fin tant que
tab[varB+1] ← k
varA ← varA + 1
fin tant queEst-ce que les 2 boucles sont bornées ?
Cette question est importante, car si une boucle n'est pas bornée, il est possible que le programme ne se termine pas !
On parle de justifier de la terminaison de l'algorithme.
À ne pas confondre avec la preuve que l'algorithme fonctionne !
Comment échanger 2 variables ?
La variable k permet de mémoriser une des 2 valeurs à échanger, comme si c'était une mémoire temporaire le temps de l'échange comme le montre le schéma ci-dessous :
En 3 étapes, l'échange des valeurs peut se faire
Faire tourner l'algorithme sur un exemple
Vous allez tester l'algorithme à la main en prenant comme valeurs tab[ 44, 73, 81, 52, 28, 22, 21, 87] et varA=3 afin de faire les mêmes étapes que l'exemple ci-dessus.
Quelles sont les valeurs de varA et varB pour lesquelles les 2 boucles s'arrêtent ?
Complexité
Quelle est la complexité de cet algorithme puisqu'il y a 2 boucles imbriquées ?
Pyhton
Pour ceux qui veulent : réaliser en python le programme correspondant et lancez-le afin de vérifier le résultat.
Exercice
Soit l'algorithme ci-dessous que vous devez faire tourner à la main.
Les colonnes bleues correspondent à la partie bleue de l'algorithme.
Compléter les valeurs au fur et à mesure que vous faites tourner l'algorithme à la main sans mettre d'espace.
Les 4 premières colonnes sont à compléter systématiquement.
Les 3 dernières colonnes sont à compléter si les instructions correspondantes sont exécutées.
