Trier de trés grosses tables

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 :roll:

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?

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...

Le tri rapide comme son nom l'indique est rapide :mouarf:
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à :P

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

Citation:

---

Envoyé par funckfot

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 ) :koi: ?

Citation:

---

Envoyé par pseudocode

ORDER BY UPPER( some_name ) :koi: ?

---

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

qsort ??

ou sort (shell) sous *n*x

Citation:

---

Envoyé par shawn12

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

Citation:

---

Envoyé par souviron34

qsort ??

ou sort (shell) sous *n*x

---

Rien compris !!!:roll:

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) :aie: .. C'est ce qu'on t'a signalé sous le nom "tri rapide"..

[/EDIT]

Zao,

Citation:

---

Envoyé par funckfot

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

Citation:

---

Envoyé par funckfot

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

Citation:

---

Envoyé par pseudocode

ET tu les veux où les chiffres ? avant ?

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

---

SUPER :king: 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

Citation:

---

Envoyé par droggo

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.