J'ai vu un programme en Qbasic qui permettait de comparer les performances des differents algos de tris.
Je voudrait le retrouver.
 
A moins que qq puisse me passer tous ces algos de tris que je le fasse moi meme en C...
 
Merci !

pour les tris (les plus courants)
 
*bubble sort
tu considère tes données rangées, et tu les parcours. Si deux éléments adjacents sont dans le mauvais ordre, tu échages leurs places. Tu répètes jusqu'à ce que tu ne fasses plus d'échanges.
 
complexité temps O(n2) merdique
 
 
*quicksort
tu prends tes données.
S'il n'y a qu'un élem tu le renvois
tu en choisis une au pif dedans (pivot).
tu crées deux array: les plus petits que le(ou égaux au)pivot
et les plus grands, et tu les appelle P et G.
tu appelles quicksort sur P et G.
tu concatènes P,pivot et F et tu renvois le résultat
 
complexité nlogn en moyenne, mais n2 dans le pire cas (rarissime qd tu choisis le pivot au pif)
 
*mergesort
prendre deux array triés et les fusionner en un est de complexité n et est facile à faire.
 
donc mergesort
s'il n'y a qu'un élem, on le renvoit.
sinon on coupe en deux (AetB).
On mergesort A et B.
on fusionne A et B et on renvoit le résultat
 
cplx nlogn
*heapsort
Je peux te le décrire, mais c'est plus long. Y'a un arbre dans lequel on insère les éléments pris séquentiellement et on s'assure que le fils gauche est plus grand que le noued lui même plus grand que le fils droit. Et ensuite on vide l'arbre et on concatène les morceaux.
 
C'est un arbre de recherche. L'avatage est que l'insertion dans une telle structure est rapide
 
cplx nlogn
 
*insertsort
tu insères chaque élément dans sa place dans une liste.
 
cplx n2
 
*shuffle-sort
tu prends les données, si elles sont triées tu les renvoies, sinon tu les mélanges au pif et tu recimmences.
Complexité moyenne Ann

Merci!
ça me fait un excellent rappel !  

au niveau rapport facilié d'implémentation/rapidéité d'exécution, je trouve que le tri par insertion est le mieux... Maitenant, c'est vrai que le Qsort est vachement rapide.
 
par contre, j'ai pas trop compris le mergesort. Tu dis qu'il est en cplx n?

Le tri par insertion est de complexité merdique, attention, sauf si l'on utilise des structures de données à comportement mixte.
 
Qsort est facile à implémenter et est très rapide, mais sa vitesse peut varier en fonction du conditionnement des données initiales, et c'est pour ça qu'il n'est pas toujours utilisé.
 
Mergesort est en cplx O(n(log(n))) et non n.
D'ailleurs, y'a pas d'algo de tri avec une complexité moyenne inférieure à n.
 
Démonstration:
si t'as n objets, y'a Ann façons de les ranger au pif, c'est à dire n! (factorielle) arrangements.
 
Trier les objets, revient à trouver l'arrangement pour lequel les objets sont dans l'ordre.
 
Une comparaison entre deux objets renvoit un résultat binaire:
 
soit a et b
a<b est soit vrai soit faux
 
donc une comparaison permet de découper l'ensemble des arrangements en deux.
 
Soit A0, l'ensemble des arrangements possibles, et C0 la première comparaison que l'on va faire.  
Pour chaque arrangement de A0, C0 est soit vrai soit faux. On définit donc une partition de A0 que l'on appelle
A0(vrai)
et
A0(faux)
 
si C0 est vrai, alors on pose A1=A0(vrai)
sinon on pose A1=A0(faux).
et on recommence avec un test C1..
 
à chaque itération on coupe en deux le combre d'arragements correspondant possiblement à un tri bien fait.
Pour arriver à un bon arrangement (imaginons qu'il soit unique), il faut donc
log2(n!) comparaisons.
 
et il se trouve que quand n tend vers l'infini,  
log2(n!) est un O exact de n(log(n)), c'est à dire qu'il existe
A réel positif tel que log2(n!)~n(log(n)) (équivalence)
 
donc y'a pas moyen de trier avec une compléxite en comparaisons inférieure à nlogn. Pas besoin de chercher.
 
Il exite en revanche plein d'algos en nlogn, donc il faut se concentrer sur ceux-ci et oublier ceux en n2 dont la vitesse est catastrophique.
Optimiser en assembleur en tri en n2, fait partie des trucs stupides que l'on observe souvent. C'est un peu comme s'aiguiser les dents pour scier du bois. Quelque soit le degré de maîtrise atteint, ça va moins vite qu'une tronçonneuse.
 
Ne rigolez pas, j'ai vu récemment des étudiants travaillant sur le parallélisme produire du code à complexité plus élevé pour qu'il soit lent pour que ça vaille la peine d'utiliser des machines multiprocesseur!

Le tri par fusion est un des plus simples à expliquer et il est récursif.
 
on considère une fonction qui fusionne deux listes déjà triées en ordre croissant
 
liste fonctionfusion(liste l1, liste l2)
{
liste resultat
while(l1.PasVide et l2.PasVide)  
 if(l1.premierelem<liste2.premierelem)
  {
   resultat.ajouteralafin(l1.premierelem);
   l1.enleverpremierelem
  }
  else
  {
   resultat.ajouteralafin(l1.premierelem);
   l1.enleverpremierelem
  }
resultat.concatene(l1)
resultat.concatene(l2)
renvoit resultat
}
 
soit une liste de données initiales.
 
liste trifusion(liste initiale)
{
if (listeinitiale.taille<=1)
 renvoit listeinitiale
else
{
 coupe listeinitiale en deux morceaux l1 et l2
 l1=trifusion(l1)
 l2=trifusion(l2)
 renvoit l1.concatène(l2)
}
}
 
et voilà!

Dans quasiment toute les sortes de tri, il est plus rapide de trier un tableau de pointeur que le tableau lui même contenant des éléments lourds a deplacer...
 
le pire c le tri conffusion.