Principe : Construire une nouvelle liste par insertion successive des éléments de la liste d'origine dans la liste résultat. La liste résultat commence donc avec un unique élement et reste en permanence triée.
La recherche de la place d'insertion se fait par un algorithme de recherche simple.
|
Complexité : O(n^2) comparaisons |
|
/* Tri en copie de la liste tab
de taille longueur avec construction de la liste resultat
de taille longueur_resultat */
|
| resultat[0] <== tab[0] |
| longueur_resultat <== 1 |
| Répéter pour i allant de 1 à longueur |
| place <== recherche_simple(resultat, tab[i]) |
| /* décalage des éléments de resultat depuis la fin jusque "place" */ |
| Répéter pour j allant de longueur_resultat à place+1 |
| resultat[j] <== resultat[j-1] |
| fin_de_répéter |
| /* insertion de l'élément et incrément de la taille */ |
| resultat[place] <== tab[i] |
| longueur_resultat <== longueur_resultat + 1 |
| fin_de_répéter |
Principe : Construire une nouvelle liste par insertion successive des éléments de la liste d'origine dans la liste résultat. La liste résultat commence donc avec un unique élement et reste en permanence triée.
La recherche de la place d'insertion se fait par un algorithme de recherche dichotomique .
|
Complexité : O(n log(n)) comparaisons |
|
/* Tri en copie de la liste tab
de taille longueur avec construction de la liste resultat
de taille longueur_resultat */
|
| resultat[0] <== tab[0] |
| longueur_resultat <== 1 |
| Répéter pour i allant de 1 à longueur |
| place <== recherche_dichotomique(resultat, tab[i]) |
| /* décalage des éléments de resultat depuis la fin jusque "place" */ |
| Répéter pour j allant de longueur_resultat à place+1 |
| resultat[j] <== resultat[j-1] |
| fin_de_répéter |
| /* insertion de l'élément et incrément de la taille */ |
| resultat[place] <== tab[i] |
| longueur_resultat <== longueur_resultat + 1 |
| fin_de_répéter |
Principe : Partir de la fin (resp. du début) et faire remonter, par permutations successives (comme une bulle), le plus petit élément (resp. le plus grand) en tête (resp. queue) de liste.
|
Complexité : O(n^2) comparaisons |
|
/* Tri en placede la liste tab
de taille longueur */
|
| Répéter pour i allant de 0 à longueur - 1 |
| Répéter pour j allant de longueur - 1 à i+1 |
| si tab[j] < tab[j-1] |
| /* permutation des éléments tab[j] et tab[j-1] */ |
| alors tmp <== tab[j] |
| tab[j] <== tab[j-1] |
| tab[j-1] <== tmp |
| fin_de_répéter |
| fin_de_répéter |
|
/* Tri en placede la liste tab
de taille longueur */
|
| Répéter pour i allant de 0 à longueur - 1 |
| Répéter pour j allant de longueur - 1 à i+1 |
| si tab[j] < tab[i] |
| /* permutation des éléments tab[i] et tab[j] */ |
| alors tmp <== tab[j] |
| tab[j] <== tab[i] |
| tab[i] <== tmp |
| fin_de_répéter |
| fin_de_répéter |
Principe : Construire une nouvelle liste par sélection successive du plus petit élément de la liste d'origine, suppression de cet élément de la liste d'origine et insertion en fin de liste triée.
|
Complexité : O(n^2) comparaisons |
|
/* Tri en copie de la liste tab
de taille longueur avec construction de la liste resultat
de taille longueur_resultat */
|
| longueur_resultat <== 0 |
| Répéter |
| /* Recherche de l'indice du minimum */ |
| mini <== 0 |
| Répéter pour i allant de 1 à longueur - 1 |
| si tab[i] < tab[mini] |
| alors mini <== i |
| fin_de_répéter |
| /* insertion de l'élément et incrément de la taille */ |
| resultat[longueur_resultat] <== tab[mini] |
| longueur_resultat <== longueur_resultat + 1 |
| /* suppression de l'élément d'indice mini */ |
| Répéter pour i allant de mini à longueur - 2 |
| tab[i] <== tab[i+1] |
| fin_de_répéter |
| longueur <== longueur - 1 |
| tant que (longueur > 0) |