Programmation algorithmique/Tris

Programmation algorithmique

• Introduction
• Nombre d'opérations optimal
• Mathématiques simples
• Tableaux : parcours, recherches
• Tris de tableaux
• Structures de données
  • Listes simplement chaînées
  • Listes doublement chaînées
  • Arbres

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

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 : 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: $O(n^{2})$

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
          temp := t[i]
          t[i] := t[i+1]
          t[i+1] := temp
          nb <- nb + 1
        fin si
    fin pour
jusqu'à nb = 0

Tri par insertion

Paramè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

On 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 $O(log(n))$.
• Complexité en temps : $O(n.log(n))$ en moyenne, $O(n^{2})$ dans le pire cas.
• Nom anglais : quicksort.

Tri fusion

• Complexité en temps : $O(n.log(n))$
• Nom anglais : merge sort.

Tri par tas

• Complexité en temps : $O(n.log(n))$
• Nom anglais : heapsort.

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]+"");
		}	
	}	
}

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

Tri de Shell

• Complexité en temps : la complexité en temps de ce tri dépend de son paramétrage et, selon les cas, on trouve $O(n^{2})$, $O(n^{3/2})$, ou $O(n^{4/3})$ 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

Cette 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).