quel est le meilleur algo de tri de liste ?

bjr
j'ai parcouru des sites sur le net pour trouver le meilleur algo de tri et je vais utiliser "Shell Sort" sur lequel ils indiquent le temps de parcourt =
O(N(logN)2)
quelqu'un peut m'expliquer cette formule (surtout le "O") (et c'est pour une liste de 30000 par exemple)
et est-que c'est le meilleur algo de tri pour la rapidité de calcul et pour des listes d'une moyenne de 30000 et pouvant aller à des millions de lignes au maximum (mais c'est rare donc vaut mieux priviligier un algo qui aurait plus de perf sur des listes d'une moyenne de 30000)?
merci d'avance.

bonjour, si je me souvient bien le O ne veu pas dire grand chose, c'est la norme la complexité du tri s'exprime en O de ...
la c'est un tri qui augmente lorgarithmiquement par rapport au nombre d'element de ton tableau, le log peut etre plus ou moins fort selon le coef associé...

Pour ton tri de chaine, je dirai un tridichotomique qui si je me rapelle bien est tres performant pour les listes a taille consequente

Bon courage

ça n'a pas sa place ici, il fallait poster dans la partie Algorithmes

La notation grand O est utilisée pour mesurer la complexité d'un algorithme. Elle donne un ordre de grandeur du nombre d'instructions à exécuter en fonction du nombre d'éléments à traiter (N). C'est une borne supérieure en pire cas.

Il n'existe pas de tri le plus efficace au sens strict.
Certains tris sont plus performants à partir d'une taille donnée.

Le tri par bulle, le tri par insertion et le tri par sélection sont en O(n²)
ça signifie que pour une liste de 30000 éléments, dans le pire des cas, il faudra 900'000'000 opérations.

Il existe des tris plus évolués, tels que Quick Sort, Merge Sort, Heap Sort, qui sont en O(n log (n)).
Pour 30000 éléments il faudra donc environ 1'630'000 opérations

Enfin des tris en O(n) existent, mais necessitent l'utilisation d'une deuxieme liste de taille égale à celle qu'on veut trier

http://fr.wikipedia.org/wiki/Tri

Citation:

---

Envoyé par hamster

La notation grand O est utilisée pour mesurer la complexité d'un algorithme. Elle donne un ordre de grandeur du nombre d'instructions à exécuter en fonction du nombre d'éléments à traiter (N). C'est une borne supérieure en pire cas.

---

Avant tout, les notations O(f) et o(f) sont des notations mathématiques introduites par Landau.

O(f) signifiant de l'ordre de grandeur de la fonction f
o(f) signifiant négligeable devant la fonction f.

Cordialement
Loran

Attention, toutefois : le tri de liste et le tri de tableau ne fonctionnement pas DU TOUT de la même manière !!
Typiquement, même sur une liste doublement chaînée, le QuickSort est totalement inefficace car le temps de parcours "carbonise" le gain de l'algorithme... :-(

Pour une liste, l'insertion d'un élément ne coûte pas "cher" en performances, alors que dans un tableau, c'est le pire des cas.
Inversement, accéder à n'importe quel élément d'un tableau ne coûte pas plus "cher" qu'il soit en début ou fin, alors que sur une liste...

La problématique est exactement la même que pour le tri de fichiers "séquentiels" : je crois me rappeler que le tri par fusion était le plus performant à ce petit jeu.

Dans ton cas, surtout si tu sais que ta liste n'est pas triée, tu peux optimiser la séparation de ta liste en deux en prenant un élément sur deux (au lieu de prendre les N/2 premiers)...

Si tu te débrouilles bien, tu ne dois avoir besoin de ne modifier QUE le chaînage de ta liste pendant le tri, et tu ne devrais quasiment pas consommer de mémoire en dehors de celle utilisée par la récursivité.

Une page que j'apprécie particulièrement :
http://www.dailly.info/algorithmes-de-tri/index.php

Pour en revenir a la notation O:

- O(n) est une majoration, cela signifie que dans le pire des cas, l'algorithme aura une complexité n (comme l'a dit hamster)
- θ(n) est la complexité exacte de l'algorithme
- Ω(n) est une minoration, c'est a dire que l'algorithme aura au moins une complexité en n.

En fait pour être clair, O devrait théoriquement être la notation de Landau et g(n)=O(f(n)) signifier exactement :

Code:

---

1 2	pour tout N entier, il existe A réel strictement positif tel que pour tout n >= N, g(n) <= A*f(n)

---

Mais en réalité les notations varient selon les livres et les auteurs... Donc O() peut parfois désigner une équivalence, parfois une borne supérieure, etc.

Le shell sort est complexe à mettre en place, et n'est pas le plus performant, donc...

Comme l'a rappelé Mac LAK, les tableaux et les listes chainées ne se trie pas de la même façon : shématiquement le tri le plus utilisé pour les tableaux est le quicksort (tri rapide) et le tri le plus utilisé pour les listes est le merge sort (tri par fusion). Tous deux ont des performances moyennes en O(n*log(n) ) mais le tri fusion est plus "stable" que le quicksort car celui-ci peut atteindre du O(n^2) dans le pire des cas (si la liste est déjà presque triée) tandis que le tri fusion reste en O(n*log(n)).

Les tri en O(n) sont limités à des cas particuliers, par exemple le tri par tas, qui demande un tableau auxiliaire de la taille de l'ensemble des données possibles à trier (par exemple si tu tries sur l'ensemble des entiers naturels inférieur à 1000, tu auras besoin d'un tableau auxiliaire de longueur 1000, quelle que soit la taille du tableau à trier).

--
Jedaï

Citation:

---

Envoyé par hamster

La notation grand O est utilisée pour mesurer la complexité d'un algorithme. Elle donne un ordre de grandeur du nombre d'instructions à exécuter en fonction du nombre d'éléments à traiter (N). C'est une borne supérieure en pire cas.
Le tri par bulle, le tri par insertion et le tri par sélection sont en O(n²)
ça signifie que pour une liste de 30000 éléments, dans le pire des cas, il faudra 900'000'000 opérations.

Il existe des tris plus évolués, tels que Quick Sort, Merge Sort, Heap Sort, qui sont en O(n log (n)).
Pour 30000 éléments il faudra donc environ 1'630'000 opérations

---

Je ne suis pas spécialiste de la complexité.

Mais, bon, j'aimerais bien mettre mon grain de sel quand même.
Si un algorithme A demande n² opérations pour s'effectuer et un autre 1000000 n², on dira que l'un et l'autre sont en O(n²). Par conséquent, l'expression "tel algorithme est en O(n²)" ne donne pas une idée du nombre d'opérations à utiliser. Elle indique simplement, si N désigne le nombre d'opérations à effectuer, que lorsque n tend vers l'infini, le rapport N/n tend vers une constante C qui peut être gigantesque ou très petite.

C'est la raison pour laquelle :

Citation:

---

Envoyé par hamster

Il n'existe pas de tri le plus efficace au sens strict.
Certains tris sont plus performants à partir d'une taille donnée.

---

Le tri à bulles n'a pas de concurrent pour n=3. Par contre il est archi nul dès que n augmente (100,1000,10000) précisément parce qu'il est en O(n²), alors que le Quicksort voit son temps de calcul augmenter presque proportionnellement à n - en général -.

En outre, cela n'indique pas le "pire des cas". Cela peut caractériser le comportement "moyen", ou le comportement "le meilleur" ou le comportement "le pire" d'un algorithme selon les données qui lui sont fournies. On dira par exemple que le Quicksort est en O(nlog(n)) "en général", mais qu'il est en O(n²) dans le pire des cas (exceptionnel).

Cela dit, il est bien possible que le Quicksort demande effectivement n*log(n) opérations ; simplement l'expression "le Quicksort est en O(nlog(n))" ne le dit pas ; elle dit simplement que le nombre d'opérations du Quicksort est C*n*log(n) sans préciser la valeur de C.
Si un algorithme est en O(nlog(n)) le nombre d'opérations sera C1*n*log(n). Si un autre algorithme est en n² le nombre d'opérations sera C2*n².
Il est clair qu'on trouvera toujours une valeur de n assez grande pour que le premier aille plus vite que le deuxième. Toute la question repose sur les valeurs relatives de C1 et C2. A priori, même si C1 et C2 sont assez différents, quand n=30000, n²=900 000 000 et nlog(n) environ 300000. Même sans connaître C1 et C2 on peut bien supposer que pour n=30000 il n'y aura pas photo, c'est le premier qui gagnera.