Le meillieur algo de tri pour des nombres?

[Argorate]

Hello,

Je suis entrain de me poser une question un peu bébette, mais je voulais savoir quel est selon vous l'algo le plus performant en php pour le tri de nombre relativement peu élevé?

Merci.

[Allwise]

Pas selon mais selon Wikipedia :
http://fr.wikipedia.org/wiki/Algorithme_...s_en_place

[Argorate]

J'aurais préféré un avis parce que tu as déjà était dans un cas similaire^^

Surtout que je suis dans un cas très simple < 5 éléments.
Donc c'est sans doute pas la peine de déployer un quickshort juste pour ça non?

[Sephi-Chan]

Pourquoi ne pas utiliser la fonction native de PHP, sort() ?


Sephi-Chan

[Argorate]

Moi je vois rien contre, mais justement une partie de la question c'est es-ce qu'il y a mieux?
D'autant plus qu'il n'est pas donnée la Complexité asymptotique au pire des cas. C'est dur de comparé au niveau performance quand on ne donne pas la complexité

Curiosité: C'est basé sur quel algo cette fonction?

[Sephi-Chan]

Curiosité: C'est basé sur quel algo cette fonction?

C'est écrit dans les notes, sous les exemples…

Note: Like most PHP sorting functions, sort() uses an implementation of » Quicksort.

Moi je vois rien contre, mais justement une partie de la question c'est es-ce qu'il y a mieux?
D'autant plus qu'il n'est pas donnée la Complexité asymptotique au pire des cas. C'est dur de comparé au niveau performance quand on ne donne pas la complexité

Tu dis avoir moins de 5 nombres à trier. Est-ce réellement utile de considérer les performances, dans un tel cas ?
Une implémentation d'un algorithme — même supposé plus efficace (je doute qu'un algorithme soit plus efficace qu'un autre sur un échantillon si petit) — arrivera-t-elle à dépasser les performances d'une fonction native ?


Sephi-Chan

[Melimelo]

Sur des échantillons si petit la différence de performance doit vraiment être minimes si pas inexistante ...

[Argorate]

C'est pas une question de performance effective mais de performance théorique. Quitte a faire les choses autant les faire bien, donc justement j'étais curieux de savoir l'outil le plus approprié dans ce cas.

PS: effectivement j'avais pas vu que ça venait du Quicksort, ça peut donc être assez intéressant.
Si j'y pense (et si je le temps) je regarderais si c'est plus rapide que l'implémentation pur et dure du Quicksort que j'avais fait il y a quelques mois.

Merci, pour le moment ça me convient vu les performances de Quicksort.

[Sephi-Chan]

Ah ok, c'était de la branlette quoi !


Sephi-Chan

[Allwise]

J'aurais préféré un avis parce que tu as déjà était dans un cas similaire^^

Surtout que je suis dans un cas très simple < 5 éléments.
Donc c'est sans doute pas la peine de déployer un quickshort juste pour ça non?

Tu cherches l'algo de tri le plus rapide sur de petits échantillons de données. Je te donne un article qui compare la performance des algos de tri sur de petits, moyens, et grands volumes. What the buck ?

Je me suis jamais posé la question parce que je ne trie jamais des tableaux de plusieurs milliers d'enregistrements. Pour l'usage courant les fonctions natives me suffisent, je m'attarde pas à chercher de la perf sur ça, pour les petits volumes y a rien à prendre...
Comme dit Sephi, je doute qu'il y ait plus rapide que les fonctions natives du langage sur des petites taches comme ça.

Pour des traitements plus lourds ça vaut le coup de se poser la question. Mais un petit tri ça passe comme une lettre à la poste