vendredi 6 janvier 2012

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

0 commentaires:

Enregistrer un commentaire

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites

 

IP