TRI ULTRA RAPIDE NON RÉCURSIF
PCPT
Messages postés
13272
Date d'inscription
lundi 13 décembre 2004
Statut
Membre
Dernière intervention
3 février 2018
-
14 déc. 2008 à 14:48
CGSI3 Messages postés 416 Date d'inscription vendredi 22 février 2008 Statut Membre Dernière intervention 7 janvier 2018 - 15 déc. 2008 à 09:08
CGSI3 Messages postés 416 Date d'inscription vendredi 22 février 2008 Statut Membre Dernière intervention 7 janvier 2018 - 15 déc. 2008 à 09:08
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/48709-tri-ultra-rapide-non-recursif
https://codes-sources.commentcamarche.net/source/48709-tri-ultra-rapide-non-recursif
15 déc. 2008 à 09:08
15 déc. 2008 à 01:40
bonne continuation
14 déc. 2008 à 23:56
Elle se comporte différement aussi avec les listes triees, avec une nouvelle version elle devrait montrer quelques avantages dans ce domaine.
Je l'ai conçu pour trier tout type de liste ( variant, texte, date, nombre...), c'est pourquoi je ne defini aucun parametres.
Merci pour tout !
CGSI3
14 déc. 2008 à 22:38
Public Sub Tri_Vague(Liste() As Long)
Dim EcartMem As Long, Ecart As Long, f As Long, t As Long
Amicalement,
Us.
14 déc. 2008 à 22:24
Ok. Bien meilleur cette fois. Mais ne rivalise toujours pas avec QuickSort.
En vb6 après compilation, QuickSort resort 25 fois plus rapide environ...
(D'ailleurs, ton algo n'est pas sans rappeler celui de QuickSort par certains côtés).
Amicalement,
Us.
14 déc. 2008 à 20:16
EcartMem (c - b) \ 2: Ecart EcartMem: oZZ = True
14 déc. 2008 à 19:01
Pour le temps d'execution je reste perplexe vis a vis des 138 Secondes, Sur un PC récent, je trie 27000 éléments d'une liste en 1060 Millisecondes.
J'ai essaye un tri fusion 15023 Millisecondes,
un tri quicksort 1800 MilliSecondes
, je verifie donc tous les éléments que vous m'avez transmis, et les fonctions quicksort et trifusion que j'ai trouvé et je vous redonne mes conclusions
14 déc. 2008 à 18:17
http://www.cppfrance.com/code.aspx?id=48711
14 déc. 2008 à 18:00
D'après mes premiers tests, la vitesse de tri n'est pas bonne du tout. Le tri QuickSort reste de loin le plus rapide. (voir sur codyx http://www.codyx.org/snippet_tri-nombres_421.aspx#1617).
De plus, si quicksort était non récursif alors il serait encore plus rapide...
Ensuite, le temps du tri de cette algo n'est pas proportionnel au nombre à trier... Ce qui fait que si avec 1000 éléments, le temps est raisonnable (1,25s), pour 10000 cela devient vraiment non acceptable... 138 secondes... c'est à dire un facteur 100. C'est problématique.
Pour avoir tester divers algo de tri, le seul vraiment bon, c'est le QuickSort dans tous les cas. (On peut faire mieux comme algo que dans un cas spécifique.)
Amicalement,
Us.
14 déc. 2008 à 14:48
pour les "bouts de code" comme celui-ci, fonctions pratiques prêtes à l'emploi, il est préférable de poster sur www.codyx.org (même login/pass), tant pour VB que C++ et autres
merci