Pages - Menu

Pages

Algorithmes de Tri : Tri par Insertionn par Sélection, par Fusion, Rapide, Tri à Bulles avec des Exemples

Les tris

Idée fondamentale

  • Une collection de valeurs de même type (rangées dans un tableau)
  • Un opérateur de comparaison (=,=, >, <, …)
  • But :
  • Ré-ordonner les valeurs de la façon suivante
o   T[i] = T[i+1] ? i ? [1 .. Taillemax]

Quelques algorithmes de tris
  • Tris élémentaires
o   Tri par insertion
o   Tri par sélection
o   Tri par permutation
  • Tris avancés
o   Tri Fusion
o   Tri rapide
  • Borne Inférieure sur le tri par comparaison

Tri par insertion
  • Tri interne, sur place et par comparaison
  • Principe :
o   A tout moment, le tableau à trier sera en 2 parties :
- Une partie triée  [1 .. TailleCourante]
- Une partie non triée [TailleCourante+1 .. TailleMax]


Tri par insertion
  • Principe :
o   Prendre un élément non encore trié
o   L’insérer à sa place dans l’ensemble des éléments triés
 
    
Tri par insertion – Algorithme –

TriParInsertion(T : Tableau d’entiers, TailleMax : entier)
Entrées : T(tableau d’entiers), TailleMax (taille du tableau)
Sortie : Tableau trié T
Début
TC, p, temp : entier;
Pour  TC de 1 jqa TailleMax -1 faire
temp ? T[TC+1];
p ? 1;                                     //  Chercher la position p
Tant que T[p] < temp faire
p ? p + 1;
Fin Tant Que
Pour i de TC en décroissant jqa p
T[i+1] ? T[i]               // Décaler les éléments
Fin Pour
T[p] ? temp;
Fin Pour
Fin

Tri par insertion
  • Complexité :
o   Le corps de la boucle est exécuté n-1 fois
o   Une itération :
- Recherche de la position  : p
- Décalage des éléments :  TC – p
- Total : TC
o   Au total :

o   Complexité : O(n2)
o   Dans le meilleur des cas quand le tableau est totalement trié, le tri par insertion est linéaire.
o   Amélioration : Recherche dichotomique : ? (n log2 n)

Tri par insertion : Exemple


Tri par sélection
  • Principe général :
o   Tableau toujours divisé en 2 parties
o   A chaque étape,
-  Choisir le plus petit élément de la partie non triée
-  Mettre cet élément à la fin de la partie triée

Tri par sélection – Algorithme – 

TriParSelection(T : Tableau d’entiers, TailleMax : entier)
Entrées : T(tableau d’entiers), TailleMax (taille du tableau)
Sortie : Tableau trié T
Début
TC, p, min,temp : entier;
Pour  TC de 1 jqa TailleMax -1 faire
min ? T[TC];
p ? TC;
Pour i de TC+1 jqa TailleMax faire
Si T[i]< min alors
min ? T[i];          //  Rechercher l’élément min
p ? i;
Fin Si
Fin Pour
temp ? T[p];
T[p] ? T[TC];
T[TC] ? temp;                           // Le mettre à la fin des éléments triés
Fin Pour
Fin

Tri par sélection
  • Complexité :
o   Nombre d’itérations : n-1
o   A chaque itération :
-  Recherche du minimum : n-TC
-  Mettre l’élément à sa place : 3
  • Au total : 3n + n(n-1)/2
  • Complexité : O(n2)
Tri par sélection : Exemple



Tri par permutations (tri à bulles)
  • Idée Simple :
o   Si 2 éléments voisins ne sont pas ordonnés on les échanges
  • Deux parties dans le tableau :
o   Les éléments de la partie triée sont inférieurs aux éléments de la partie non triée.
 

Tri par permutation  - Algorithme – 

TriParPermutation(T : Tableau d’entiers, TailleMax : entier)
Entrées : T(tableau d’entiers), TailleMax (taille du tableau)
Sortie : Tableau trié T
Début
     i,j : entier;
     Pour  TC de 2 jqa TailleMax faire
          Pour i de TailleMax en décroissant jqa TC faire
                    Si T[i-1]> T[i] alors
                              T[i-1]? T[i];
                    Fin Si
          Fin Pour
     Fin Pour
Fin

Tri par permutation
  • Complexité :
o   Boucle externe : n-2 fois
o   Boucle interne : TailleMax-TC fois
o   Total : (n-1)(n-2)/2
  •  O(n2)
Tri par permutation : Exemple



Permutations
  • Départ une permutation aléatoire p de n valeurs
  • Soit p la permutation inverse
  • Soit (x,y) une paire quelconque pris dans p tels que x < y
  • Cette paire est une inversion dans p ou dans p
  • Nombre de paires dans une permutation : n(n-1)/2
  • En moyenne une permutation aléatoire contiendra n(n-1)/4 paires
Tous les Algos basés sur des échanges d’elts adjacants sont O(n2)

Tri Fusion
  • Machine  à trier des cartes perforées en 1938
  • 1er algo de tri fusion écrit par Von Neumann pour l’EDVAC en 1945
  • Basé sur le paradigme
« Diviser pour Régner »

Diviser pour Régner
  • Séparer le problème en plusieurs sous-problèmes similaires au problème initial
  • 3 étapes :
o   Diviser : le problème en un certain nombre de sous-pb
o   Régner : sur les sous- problèmes en les résolvant
o   Combiner : les solutions des sous- problèmes en une solution unique.

Tri Fusion
  • 3 étapes :
o   Diviser :
-  La séquence de n éléments à trier en 2 sous-séquences de n/2 éléments.

o   Régner : Toute séquence de longueur 1 est triée
-  Trier les 2 sous-séquences récursivement à l’aide du tri fusion

o   Combiner : Action Principale : la fusion
-  Fusionner les 2 sous-séquences triées pour produire la séquence triée.

La fusion : Algorithme 

Fusion(T : Tableau d’entiers,p: entier, q: entier, r:entier)
Entrées : T(tableau d’entiers), p,q et r (indices du tableau tels que p = q < r)
Sortie : Tableau trié T entre les indices p et r
Pré-condition : T[p..q-1] et T[q..r] sont triés

Début
      i,j,k : entier;
      B : tableau d’entiers
      i ? p; k ? p; j ? q;
      Tant que (i < q et j = r) faire
                  Si T[i]< T[j] alors
                              B[k]? T[i];
                              i ? i + 1;
                  Sinon
                              B[k]? T[j];
                              j ? j + 1;
                  Fin Si
                  k ? k + 1;
Fin Tant Que
Tant que (i < q) faire
              B[k]? T[i];
              i ? i + 1;
              k ? k + 1;
Fin Tant Que
              Tant que (j = r) faire
              B[k]? T[j];
              j ? j + 1;
              k ? k + 1;
Fin Tant Que
T ? B
Fin

Tri Fusion : Algorithme 

TriFusion(T : Tableau d’entiers,p: entier, r:entier)
Entrées : T(tableau d’entiers), p et r (indices du
tableau tels que p = r)
Sortie : Tableau trié T entre les indices p et r
Début
       Si p < r
              q ? ?(p+r)/2?
              TriFusion(T,p,q)
              TriFusion(T,q+1,r)
              Fusion(T,p,q,r)
       Fin Si
Fin

Tri Fusion : Complexité
  • La preuve est technique mais
  • Intuitivement il faut résoudre : 
       o   Tri(n) = 2 * Tri(n/2) + ? (n)
  • Complexité finale : O(n log2 n)

Le tri fusion : Exemple


Le tri fusion: Exemple


Tri Rapide
  • Proposé par Hoare en 1962
  • Diviser :
o   T[p..r] est divisé en 2 sous-tableaux non vide T[p..q] et T[q+1..r] tel que :
o   Chaque élément de T[p..q] soit inférieur à chaque élément de T[q+1..r]
o   fonction Partitionner
  • Régner :   
o   2 sous-tableaux triés grâce à la récursivité
o   fonction TriRapide

  • Combiner :
o   2 sous-tableaux triés sur place : Rien à faire

La partition – Algorithme -

Partitionner(T : Tableau d’entiers, p: entier, r:entier)
Entrées : T(tableau d’entiers), p et r (indices du tableau tels que p < r)
Sortie : Tableau trié T entre les indices p et r
Début
       i,j,pivot : entier;
       i ? p;  j ? r;
       pivot ? T[p];
       Tant que (i < j) faire
              Tant que  T[i] < pivot faire
                     i ? i + 1;   //en partant de gauche le 1er élément plus grand que le pivot
              Fin Tant Que
              Tant que  T[j] > pivot faire
                     j ? j - 1; // en partant de droite le 1er élément plus petit que le pivot
              Fin Tant Que
              Si i < j
                     T[i] ? T[j];  // si il existe un élément plus petit et un élément plus grand
                     i ? i + 1;           échanger les  que le pivot
                     j ? j - 1;
              Fin Si
       Fin Tant Que
       retourner j;
Fin

Tri Rapide

TriRapide(T : Tableau d’entiers,p: entier, r:entier)
Entrées : T(tableau d’entiers), p et r (indices du tableau tels que p = r)
Sortie : Tableau trié T entre les indices p et r
Début
       Si p < r
              q ? partitionner(T,p,r);
              TriRapide(T,p,q)
              TriRapide(T,q+1,r)
       Fin Si
Fin

Tri rapide exemple


Tri rapide exemple suite


Tri rapide exemple suite



Tri Rapide : Complexité
  • Temps d’exécution dépend de l’équilibre ou non du partitionnement.
  • Si le partitionnement est équilibré : aussi rapide que le tri fusion
  • Si le partitionnement est déséquilibré : aussi lent que le tri par insertion
    
 Partitionnement dans le pire cas
  • 2 sous-tableaux de :
o   1 élément
o   n-1 éléments
  • Supposons que ce partitionnement intervienne à chaque étape.
  • Le partitionnement coûte ? (n)
  • La récurrence :
o   T(n) = T(n-1) + ? (n)
o   T(1) = ? (1)
o    T(n) = ? O(k)
o   = O(? k)
o   = O(n2)
  • Ce partitionnement apparaît quand le tableau est trié !!!!
  • Pire dans ce cas-là le tri par insertion est linéaire !!
    
Partitionnement dans le meilleur cas

  • Partitionnement est équilibré.
  • Il faut donc résoudre :
  • T(n) = 2T(n/2) + ? (n)
  • Solution : T(n) = ? (n log2 n)
Tris par comparaisons
  • tous les tris vus dans ce cours sont tris par comparaisons
  • un tri par comparaison est un tri dans lequel on compare une paire d’éléments.
  • contrairement par exemple au tri dénombrement qui est un tri linéaire

Tri linéaire
  • Exemple le tri par dénombrement
o   Soit A un tableau d’entier inférieur ou égal à 6

o   Soit C un tableau auxiliaire qui compte le nombre de fois qu’apparaît un entier

o   Soit B le tableau trié

Optimalité des tris vus en cours
  • On va montrer qu’un tri par comparaison a une complexité en ? (n log2 n)
  • Donc les tris qui ont une complexité en O(nlog2 n) sont optimaux.
  • Le tri fusion est optimal mais pas le tri rapide !
Récapitulatif



Expérimentations:

Comparaisons pour 10 valeurs
  

1 commentaire: