Discussion :

[funckfot]

Bonjours,
c 'est le genre de chose que vous avez tres souvent mais je veut connaitre l'algorithme le plus rapide pour un tri

j'ai des tables qui peuvent aller de 100 enregistrements jusqu'a 500 000 facile

et pas moyen de les metre en ordre (avec order by) car la configuration AS400 me donne en premier les minuscules, les majuscules et enfin les chiffres ( je crois que c'est le code EBCDIC (ou par la)) or mon traitement ce fait sur une plateforme JAVA 1.3

je récupere un object et je doi les comparer avec des String ou chaine de carractère


le trie par bulle est trés lent pour ce genre de tables, mais est que le tri rapide est-il vraiment rapide?

je ne peut pas télécharger le logiciel qui fait la comparaison mais apparament le tris rapide est meilleur.

et le tri fusion qu'es que c'est?

[Ekinoks]

Effectivement le tri par bulle est très long ^^ il a une complexité d'ordre N^2 (N étant le nombre d'argument)

Le tri rapide et le tri fusion on une complexité d'ordre N*log2(N).

Le tri fusion consiste à fusionner récursivement des tableaux trier.
On fusion 1 nombre avec un autre nombre, puis 2 avec 2 puis 4 avec 4 etc...

Mais bien que la complexité de ces deux tri soit identique, le tri rapide est plus efficace et demande moins de mémoire RAM que le tri fusion.


Ceci dit il y a peu étre un moyen pour que ton (order by) ne prenne pas en compte les majuscules...

[O( N )]

Le tri rapide comme son nom l'indique est rapide
Au pire c'est n² et en moyenne n*log(n)
mais ces liens parleront mieux que moi

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

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

voilà

Le réflexe google et wiki n'est pas trop mal en général !

[pseudocode]

et pas moyen de les metre en ordre (avec order by) car la configuration AS400 me donne en premier les minuscules, les majuscules et enfin les chiffres

ORDER BY UPPER( some_name ) ?

[shawn12]

ORDER BY UPPER( some_name ) ?

Oui mais les chiffres restent positionnés à la fin non ?

[souviron34]

qsort ??

ou sort (shell) sous *n*x

[funckfot]

Oui mais les chiffres restent positionnés à la fin non ?

en effet cella me le positionne les majuscule au bon endroit

mais les chiffres c'est tj parreille

[funckfot]

qsort ??

ou sort (shell) sous *n*x

Rien compris !!!

[souviron34]

je disais qsort c'est le nom de la fonction C qui fait du quick sort (http://en.wikipedia.org/wiki/Quicksort) basé sur la méthode "divide and conquer".

Et si tu es sous un système unixoide, la commande shell sort parmet de faire ça sans le programmer...

[EDIT]

Je viens de regarder.. Je suis pas habitué aux traductions des noms informatiques (d'algo en particulier) .. C'est ce qu'on t'a signalé sous le nom "tri rapide"..

[/EDIT]

[droggo]

Zao,

mais les chiffres c'est tj parreille

Ben oui, au moins pour ça, tu dépends du système d'encodage, à moins d'écrire ta propre fonction de comparaison.

Pour le tri, il vaut probablement mieux utiliser le tri par tas (heapsort), qui en moyenne est meilleur que le tri rapide (quick sort) : en n*log(n) dans le pire des cas, alors que le tri rapide va de n*log(n) à n*n dans le pire des cas

[pseudocode]

en effet cella me le positionne les majuscule au bon endroit

mais les chiffres c'est tj parreille

ET tu les veux où les chiffres ? avant ?

ORDER BY LOCATE( LEFT(some_name,1) , "9876543210") DESC, UPPER(some_name) ASC

[funckfot]

ET tu les veux où les chiffres ? avant ?

ORDER BY LOCATE( LEFT(some_name,1) , "9876543210") DESC, UPPER(some_name) ASC

SUPER sa marche mais que directement sur la machine AS400 en JAVA il accepte rien meme pas le UPPER je suis en JAVA 1.3 pour ceux qui connaisse et donc j'utilise un JDBC mais je sais pas lequelle

[Jean-Marc.Bourguet]

Pour le tri, il vaut probablement mieux utiliser le tri par tas (heapsort), qui en moyenne est meilleur que le tri rapide (quick sort) : en n*log(n) dans le pire des cas, alors que le tri rapide va de n*log(n) à n*n dans le pire des cas

Le tri rapide est en moyenne plus rapide que le heap sort. La constante est plus petite et les entrees sur lesquelles il degenere sont rares quand il est bien code (quand il est mal code, il peut degenerer sur des donnees presque triees ce qui dans certaines applications arrive souvent). heap sort n'est en fait utile que si la garantie de n log n est utile -- et dans ce cas, il vaut peut-etre mieux un adaptatif qui passe de quick sort a heap sort quand il detecte un probleme.