¿Qué algoritmos de ordenamiento aplica la aplicación de PHP?

Question

Quiero ordenar archivos por tiempo de modificación ascendente y descendente.

De acuerdo con esto answer Parece que esto se puede lograr mejor definiendo una función de devolución de llamada de clasificación y usando usort/uasort.

Sin embargo, debido a la naturaleza de mi aplicación, es probable que encuentre algunos escenarios de peor caso para algunos algoritmos de ordenación (por ejemplo, secuencia de entrada casi ordenada de forma inversa).

Como cada comparación utiliza dos accesos al sistema de archivos que están parcialmente en unidades de red, el número de comparaciones es crítico y debe minimizarse. Otros tipos de iteraciones pueden ser más.

Entonces, ¿qué algoritmos de clasificación utilizan las funciones de clasificación de matriz de PHP? ¿Ordenación rápida? Multisort? ¿Hay alguna forma de que pueda configurar esto?

¿Debo quizás barajar la matriz antes de ordenar?

¿O debo escribir mi propia implementación?

¿Conoces algunas buenas bibliotecas que ofrecen funciones de ordenación con algoritmos configurables?

¿Qué algoritmo o formas de resolver este problema de minimizar comparaciones recomendaría?

Answer 1

En php.net/sort encontré esto:

Nota: Como la mayoría de las funciones de clasificación de PHP, sort() utiliza una implementación de »ordenación rápida.

creo que utiliza un randomized quicksort, así que no hay necesidad de barajar la matriz.

¡Hice some tests y el quicksort de PHP no está distribuido al azar, así que baraje su matriz de entrada!

Answer 2

Hice algunas búsquedas usando PHP OpenGrok, y basándome en echar un vistazo a los nombres de funciones y el código de skimming, parece que usort se implementa con quicksort.

Para minimizar las llamadas al sistema de archivos, haga una vez para cada elemento en su matriz y almacene los resultados en otra matriz. Use esa segunda matriz en su función de comparación en lugar de hacer las llamadas nuevamente.