Programmation Algorithmique/Tris
Un livre de Wikibooks.
| Algorithmique |
 |
| Sommaire |
| Modifier ce modèle |
[modifier] Les algorithmes de tri
[modifier] Tri par sélection
- 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, aux : entier
pour i de 1 à N - 1
min := t[i]
indicemin := i
pour j de i + 1 à N
si t[j] < min alors
min := t[j]
indicemin := j
fin si
fin pour
aux := t[i]
t[i] := t[indicemin]
t[indicemin] := aux
fin pour
[modifier] Tri bulle
- 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
aux := t[i]
t[i] := t[i+1]
t[i+1] := aux
nb <- nb + 1
fin si
fin pour
jusqu'à nb = 0
[modifier] Tri bulle bidirectionnel
[modifier] Tri linéaire
[modifier] Tri par insertion
[modifier] Tri rapide
on cohoisit le pivot de maniere aleatoire dans le tableau. ensuite on inverse le pivot de sa position a celle du premier element du tableau(indice 1) puis on fait une comparaison avec tous les elements du tableau. S'il ya un element du tableau qui lui est superieure alors il ya echange des elements. Cette comparaison s'arretera quand l'indice gauche du tableau(ici i) sera plus grand que l'indice droit du tableau(ici j). Apres cette arret de la fonction Partitionner on retourne l'indice j et on rappel la procedure Tri_rapide
FONCTION Partitionner (A: tableau [1..n] d’entiers, p:entier, r: entier):entier Var: 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 alors temp= A[i] A[i]= A[j] A[j]= temp bool= vrai Sinon Retourner j fsi ftq Fin
PROCÉDURE Tri_rapide(A : tableau [1..n], p : entier, r : entier) Var q : entier Début Si p < r alors q= Partitionner(A,p,r) Tri_rapide(A,p,q) Tri_rapide(A,q+1,r) Fsi Fin
[modifier] Tri par base
[modifier] Tri fusion
[modifier] Tri par tas
[modifier] Tri comptage
// 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]+""); } } }
[modifier] Tri par comparaison
[modifier] Tri par dénombrement
[modifier] Tri par paquets
Tri-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
