Conplxité de tri

Complexité : présentation
Le tri fusion comporte 3 étapes : la division de l'ensemble d'éléments en deux parties, le tri des deux sous-ensembles puis la fusion des deux sous-ensembles triés. Soit un ensemble de n éléments, le coût en nombre d'opérations de la division des deux ensembles est constant dans le cas du tri de tableaux et est de n dans le cas des listes. Le coût du tri des deux sous listes est égal à 2 fois le coût du tri d'une liste de longueur n/2. Enfin, le coût de la fusion des deux sous listes triées est proportionnel au nombre d'éléments à fusionner, c'est à dire en O(n).

Les quelques algorithmes vus jusqu'à maintenant sont en O(n2). D'après les résultats ci dessus, si on note T(n) la complexité du tri fusion pour classer n éléments, on a :


Or, si la complexité du tri fusion était en O(n2), on aurait :


Ce qui est inférieur à n2 dés que n>2. Par conséquent, la complexité du tri fusion n'est pas en O(n2) mais en une valeur bien inférieure.

Complexité : calcul
Pour calculer la complexité du tri fusion, nous avons besoin du résultat suivant (qui ne sera pas démontré ici) :

Soit T(N) une suite vérifiant la relation de récurence suivante : T(N)=aT(N/b)+O(Nc).
Si a < bc alors T(N)=O(Nc)
Si a = bc alors T(N)=O(Nclogb(N))
Si a > bc alors T(N)=O(Nlogb(a))
avec logb le logarithme népérien en base b

Ici, on a (2 = 21), la complexité du tri fusion est donc en O(n*lg(n)) ou lg(n) est le logarithme népérien en base 2.

Remarque: en ce qui concerne le tri de listes, le tri fusion souffre du fait que c'est un algorithme récursif. En effet, pour se dérouler, il doit construire un grand nombre de sous listes, ce qui demande un grand espace mémoire. La complexité en espace mémoire du tri fusion est donc assez handicapante si l'espace mémoire disponible n'est pas assez grand.

1- complexité en nbre de comparaisons (plus significtif)
2- complexité en nbre d'echange(3 affectation)
=>les deux opérations les plus coûteuses et les plus significativessont:comparaisons et echanges entre les eléments d'1 tableau

Principe :
Le tri fusion est construit suivant la stratégie "diviser pour régner", en anglais "divide and conquer". Le principe de base de la stratégie "diviser pour régner" est que pour résoudre un gros problème, il est souvent plus facile de le diviser en petits problèmes élémentaires. Une fois chaque petit problème résolu, il n'y a plus qu'à combiner les différentes solutions pour résoudre le problème global. La méthode "diviser pour régner" est tout à fait applicable au problème de tri : plutôt que de trier le tableau complet, il est préférable de trier deux sous tableaux de taille égale, puis de fusionner les résultats.

L'algorithme proposé ici est récursif. En effet, les deux sous tableaux seront eux même triés à l'aide de l'algorithme de tri fusion. Un tableau ne comportant qu'un seul élément sera considéré comme trié : c'est la condition sine qua non sans laquelle l'algorithme n'aurais pas de conditions d'arrêt.

Etapes de l'algorithme :
Division de l'ensemble de valeurs en deux parties
Tri de chacun des deux ensembles
Fusion des deux ensembles

pour le tri par selection voila

l'algorithme


Code source tri par "selection"
void tri_selection(int tab[],int longueur)
{
int maxi, i;

while(longueur>0)
{
//on recherche la plus grande valeur du tableau non encore trie
maxi=0;

for(i=1;i<longueur;i++)
{
if(tab[i]>tab[maxi]) maxi=i;
}

//on echange le plus grand element avec le dernier
echanger(tab,maxi,(longueur-1));

//on traite le reste du tableau
longueur--;
}
}


Complexité
La relative simplicité de cet algorithme fait qu'on lui attribut le qualificatif d' "algorithme naïf". Cela signifie que même si l'algorithme est correct, il est trop simple pour être réellement efficace. En effet, la complexité, en nombre de comparaisons, est analogue à la complexité du tri bulle optimisé. A la première itération, sont effectuées (n-1) comparaisons. A la pième itération, sont effectuées (n-p) comparaisons. Soit une complexité en O(n2) dont le calcul exact est donné par la formule suivante.

salut
voulez vous m'indiquer svp est ce qu'on peut dire que O(n log n) est une complexité du tri par insertion
merci

Code source du tri "fusion"
void fusion(int tableau[],int deb1,int fin1,int fin2)
{
int *table1;
int deb2=fin1+1;
int compt1=deb1;
int compt2=deb2;
int i;

table1=malloc((fin1-deb1+1)*sizeof(int));

//on recopie les éléments du début du tableau
for(i=deb1;i<=fin1;i++)
{
table1[i-deb1]=tableau[i];
}

for(i=deb1;i<=fin2;i++)
{
if (compt1==deb2) //c'est que tous les éléments du premier tableau ont été utilisés
{
break; //tous les éléments ont donc été classés
}
else if (compt2==(fin2+1)) //c'est que tous les éléments du second tableau ont été utilisés
{
tableau[i]=table1[compt1-deb1]; //on ajoute les éléments restants du premier tableau
compt1++;
}
else if (table1[compt1-deb1]<tableau[compt2])
{
tableau[i]=table1[compt1-deb1]; //on ajoute un élément du premier tableau
compt1++;
}
else
{
tableau[i]=tableau[compt2]; //on ajoute un élément du second tableau
compt2++;
}
}
free(table1);
}


void tri_fusion_bis(int tableau[],int deb,int fin)
{
if (deb!=fin)
{
int milieu=(fin+deb)/2;
tri_fusion_bis(tableau,deb,milieu);
tri_fusion_bis(tableau,milieu+1,fin);
fusion(tableau,deb,milieu,fin);
}
}

void tri_fusion(int tableau[],int longueur)
{
if (longueur>0)
{
tri_fusion_bis(tableau,0,longueur-1);
}
}