Jakie algorytmy sortowania stosuje usortowanie PHP?

Question

Chcę posortować pliki według czasu modyfikacji rosnąco i malejąco.

Zgodnie z tym answer Wygląda na to, że najlepiej można to osiągnąć, definiując funkcję zwrotnego sortowania i korzystając z usort/uasort.

Jednak ze względu na charakter mojej aplikacji najprawdopodobniej natrafię na kilka najgorszych scenariuszy dla niektórych algorytmów sortowania (na przykład prawie odwrotnie uporządkowana sekwencja wejściowa).

Ponieważ każde porównanie wykorzystuje dwa dostępy do systemów plików, które są częściowo na dyskach sieciowych, liczba porównań jest krytyczna i musi zostać zminimalizowana. Inne rodzaje iteracji mogą być większe.

A więc jakie algorytmy sortowania wykorzystują funkcje sortowania PHP? Szybkie sortowanie? Multisort? Czy istnieje sposób, w jaki mogę to skonfigurować?

Czy powinienem przetasować tablicę przed sortowaniem?

Czy muszę napisać własną implementację?

Czy znasz kilka dobrych bibliotek, które zapewniają funkcje sortowania z konfigurowalnymi algorytmami?

Który algorytm lub sposoby rozwiązania tego problemu minimalizacji porównań zaleciłbyś?

Answer 1

Na php.net/sort znalazłem to:

Uwaga: Podobnie jak większość PHP funkcji sortowania, sort() wykorzystuje implementację »Quicksort.

Wierzę, że używa on randomized quicksort, więc nie ma potrzeby tasowania tablicy.

Zrobiłem some tests i quicksort PHP nie jest losowy, więc przetasuj tablicę wejściową !!

Answer 2

Zrobiłem kilka wyszukiwania przy użyciu PHP OpenGrok, i tylko w oparciu o niektóre spojrzeniu na nazwy funkcji i kod szumiące, wygląda na to, że usort jest realizowany z quicksort.

Aby zminimalizować wywołania systemowe, należy je wykonać raz dla każdego elementu w tablicy i zapisać wyniki w innej tablicy. Użyj tej drugiej tablicy w funkcji porównawczej, zamiast wykonywać połączenia ponownie.