Programmation algorithmique/Tris
Les algorithmes de tri vise à ordonnancer une séquence, en suivant un ordre total. Pour pouvoir être trié avec ces algorithmes, un ordre doit donc être établi sur les éléments à trier.
Cet ordre est implicite pour des entiers, il peut l'être moins sur des données plus complexes comme par exemple des nombres flottants ou des textes.
Les algorithmes de tri
modifierTri par sélection
modifier- Paramètre en entrée/sortie : Un tableau t de N entiers T[1..N];
- Spécifications : en sortie t doit être trié du plus petit au plus grand.
t[N] : tableau d'Entier i, j, min, temp, indicemin : Entier Pour i de 1 à N - 1 //chercher le plus petit entier entre la position i et la fin du tableau min := t[i] indicemin := i Pour j de i + 1 à N Si t[j] < min min := t[j] indicemin := j Fin si Fin pour // Échanger t[i] et t[indicemin] temp := t[i] t[i] := t[indicemin] t[indicemin] := temp Fin pour
- Intuition : On cherche (on sélectionne) le plus petit élément du tableau et on le place en début de tableau, puis on cherche le plus petit élément dans le reste du tableau et on le place en seconde position dans le tableau, et ainsi de suite.
- Complexité en temps:
Tri bulle
modifier- Paramètre en entrée/sortie : Un tableau t de N entiers T[1..N];
- Spécifications : en sortie t doit être trié du plus petit au plus grand.
t[N] : tableau d'entier i, nb, temp : entier repeter nb := 0 pour i de 1 à N - 1 si t[i] > t[i+1] alors temp := t[i] t[i] := t[i+1] t[i+1] := temp nb <- nb + 1 fin si fin pour jusqu'à nb = 0
Tri bulle bidirectionnel
modifierTri linéaire
modifierTri par insertion
modifierParamètre en entrée/sortie : Un tableau t de N entiers T[0..N]
i ,j ,x :Entiers; pour i de 1 à n - 1 debut pour # mémoriser T[i] dans x x ← T[i]; # décaler vers la droite les éléments de T[0]..T[i-1] qui sont plus grands que x j ← i; tant que j > 0 et T[j - 1] > x T[j] ← T[j - 1]; j ← j - 1; fin tant que; # placer x dans le "trou" que ça a laissé T[j] ← x; fin pour; Fin;
Tri rapide
modifierOn choisit le pivot de manière aléatoire dans le tableau. Ensuite on inverse le pivot de sa position à celle du premier élément du tableau (indice 1) puis on fait une comparaison avec tous les éléments du tableau. S'il y a un élément du tableau qui lui est supérieur, alors il y a échange des éléments. Cette comparaison s'arrêtera quand l'indice gauche du tableau (ici i) sera plus grand que l'indice droit du tableau (ici j). Après cet arrêt de la fonction Partitionner, on retourne l'indice j et on rappel la procédure Tri_rapide
FONCTION Partitionner ( A : tableau [1..n] d’Entiers, p : Entier, r : Entier) : Entier x, i, j, temp: Entier bool: Booleen Début x := A[p] i := p-1 j := r+1 bool := vrai Tant que (bool) Faire Répéter j := j-1 Jusqu'à A[j] <= x Répéter i := i+1 Jusqu'à A[i] >= x bool := faux Si i < j temp := A[i] A[i] := A[j] A[j] := temp bool := vrai Sinon Retourner j Fin si Fin tant que Fin PROCÉDURE Tri_rapide(A : tableau [1..n], p : entier, r : entier) q : Entier Début Si p < r q := Partitionner(A,p,r) Tri_rapide(A,p,q) Tri_rapide(A,q+1,r) Fsi Fin
- Complexité en espace : En raison des appels récursif, on a besoin d'une pile dont la taille est en .
- Complexité en temps : en moyenne, dans le pire cas.
- Nom anglais : quicksort.
Tri par base
modifierTri fusion
modifier- Complexité en temps :
- Nom anglais : merge sort.
Tri par tas
modifier- Complexité en temps :
- Nom anglais : heapsort.
Tri comptage
modifier// Code java :présenté par simoelma
// T.length:taille du tableau
static void triparcomptage(int T[])
{
int i,s=0,k;
int nb [] = new int [T.length];
int res [] = new int [T.length];
for(i=0;i<T.length;i++)
{
for(i=0;i<T.length;i++)
{
for(k=0;k<T.length;k++)
{
if(T[i]>T[k])
{
s++;
}
nb[i]=s;
}
res[nb[i]+1]=T[i];
s=0;
}
System.out.println("***tableau est trie***\n");
for(i=0;i<T.length;i++)
{
System.out.println(res[i]+"");
}
}
}
Tri par comparaison
modifierTri par dénombrement
modifierTri par paquets
modifierTri-paquet (A) : n := longueur(A) ; pour i de 1 à n faire insérer A[i] dans la liste B[ÎnA[i]°] pour i de 0 à n-1 faire trier la liste B[I] par le tri insertion concaténer les listes B[0], B[1], …, B[n-1] dans l’ordre
Tri de Shell
modifier- Complexité en temps : la complexité en temps de ce tri dépend de son paramétrage et, selon les cas, on trouve , , ou par exemple. Voir w:Shellsort, w:Tri_de_Shell ou The art of Computer Programming volume 3, Donald E. Knuth, Addison-Wesley.
Tri de fichiers en mémoire externe
modifierCette section concerne le tri de données trop grandes pour être stockées en mémoire vive de l'ordinateur, et étant donc stockées sur des supports physiques comme des disques durs.
Notons que les périphériques de stockage sont généralement plus lents que la mémoire vive. Par ailleurs, autrefois le support externe de référence était la bande magnétique, avec pour résultat que le temps d'accès à une donnée dépend de sa position sur la bande, alors qu'en mémoire vive, le temps d'accès aux données ne dépend pas de leur emplacement (si l'on fait abstraction des questions de mémoire tampon).