Quels sont les algorithmes de tri appliqués par PHP?

Question

Je veux trier les fichiers en fonction de l'heure de modification croissante et décroissante.

En fonction de cela answer Il semble que cela soit mieux réalisé en définissant une fonction de rappel de tri et en utilisant usort/uasort.

Cependant, en raison de la nature de mon application, je suis susceptible de rencontrer des scénarios de pire cas pour certains algorithmes de tri (par exemple, séquence d'entrée presque inversée). Parce que chaque comparaison utilise deux accès au système de fichiers qui sont en partie sur les lecteurs réseau, le nombre de comparaisons est critique et doit être minimisé. D'autres sortes d'itérations peuvent être plus.

Alors, quels sont les algorithmes de tri utilisés par les fonctions de tri de tableaux de PHP? Tri rapide? Multisort? Est-il possible de configurer cela? Est-ce que je devrais peut-être mélanger la matrice avant de trier?

Ou ai-je besoin d'écrire ma propre implémentation? Connaissez-vous de bonnes bibliothèques qui fournissent des fonctions de tri avec des algorithmes configurables?

Quel algorithme ou moyen de résoudre ce problème de minimisation des comparaisons recommanderiez-vous?

Answer 1

à php.net/sort Je trouve ceci:

Note: Comme la plupart des fonctions de tri PHP, tri() utilise une implémentation de »Quicksort.

Je crois qu'il utilise un randomized quicksort, donc il n'y a pas besoin de brouiller le tableau.

J'ai fait some tests et le quicksort de PHP n'est pas randomisé, alors mélangez votre tableau d'entrée !!

Answer 2

J'ai fait quelques recherches en utilisant PHP OpenGrok, et juste basé sur un certain regard sur les noms de fonctions et le code d'écrémage, il semble que usort est implémenté avec quicksort.

Pour minimiser les appels de système de fichiers, créez-les une fois pour chaque élément de votre matrice et stockez les résultats dans un autre tableau. Utilisez ce second tableau dans votre fonction de comparateur au lieu de faire à nouveau les appels.