tris 2° méthode (tri partie triée/partie à trier)

retour

1° méthode : Le principe est de permuter deux éléments successifs en les comparant : si le premier est plus grand il remplace le suivant. On doit réaliser une certain nombre de passages pour trier l'ensemble.

Exemple simple :

soit la liste suivante 0 5 4 2 3. Le / sépare la partie triée (en rouge) de la partie non triée (en noir).

1° passage (élément n°2) 2° passage 3° passage 4° passage

0 / 5 4 2 3 Départ (la partie triée est réduite au premier élément)
élément à insérer : 5
5>0 donc continuer avec
0 5 / 4 2 3 0 5 / 4 2 3 Départ
élément à insérer : 4
4<5 donc chercher le point d'insertion : position 2; conserver le 4;
mettre 5 à la place de 4 et 4 à la place de 5

liste = 0 4 5 / 2 3
0 4 5 / 2 3 Départ
élément à insérer : 2
2<5 donc point d'insertion : position 2; conserver le 2;
mettre le 5 à la place de 2, le 4 à la place de 5 et le 2 conservé à la place du 4

liste = 0 2 4 5 / 3
0 2 4 5 / 3 Départ
élément à insérer : 3
3<5 donc point d'insertion : position 3; conserver le 3;
mettre le 5 à la place de 3, le 4 à la place de 5 et le 3 conservé à la place du 4

liste = 0 2 3 4 5 triée

On remarquera que le nombre total de passages nécessaires est de 4 pour 5 éléments dans la liste

Algorithmes :

insérer un élément

Soit le i° élément. Soit pos la position de la partie triée (pos = i-1)
On cherche où le mettre entre l'élément 0 et l'élément j (pos étant = à i-1).
Si tab[i]>tab[pos] alors tab[i] bien placé : on passe au i+1° si il existe.
Sinon :
On cherche tant que tab[j] < tab[i] la 1°position où tab[j] >= tab[i] : c'est insert

On va donc :
mettre la valeur de tab[i] dans garde
puis de j=i à insert+1 en décrémentant : faire tab[j]=tab[j-1]
puis mettre garde dans tab[insert]

répétition du tri

Au départ i vaut 1 (la liste est triée si elle n'a qu'un élément portant le numéro 0).
La boucle ira donc de i=1 jusqu'à nbelement-1.

AVANT LE TRI

APRÈS LE TRI