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 log₂ 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(n²)

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(n²)

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(n²)

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 log₂ 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 log₂ 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 log₂ n)
• Donc les tris qui ont une complexité en O(nlog₂ n) sont optimaux.
• Le tri fusion est optimal mais pas le tri rapide !

Récapitulatif

Expérimentations:

Comparaisons pour 10 valeurs