Dlaczego metoda Arrays.sort języka Java wykorzystuje dwa różne algorytmy sortowania dla różnych typów?

Arrays.sortMetoda Java 6 wykorzystuje Quicksort do tablic prymitywów i sortowanie przez scalanie dla tablic obiektów. Uważam, że przez większość czasu Quicksort jest szybszy niż scalanie, sortowanie i kosztuje mniej pamięci. Moje eksperymenty to potwierdzają, chociaż oba algorytmy mają wartość O (n log (n)). Dlaczego więc różne algorytmy są używane dla różnych typów?

Najbardziej prawdopodobny powód: szybkie sortowanie nie jest stabilne , tj. Równe pozycje mogą zmieniać swoje względne położenie podczas sortowania; między innymi oznacza to, że jeśli posortujesz już posortowaną tablicę, może ona pozostać niezmieniona.

Ponieważ typy pierwotne nie mają tożsamości (nie ma możliwości rozróżnienia dwóch liczb typu int o tej samej wartości), nie ma to dla nich znaczenia. Ale w przypadku typów referencyjnych może powodować problemy w niektórych aplikacjach. Dlatego do tych plików używane jest stabilne sortowanie przez scalanie.

OTOH, powodem nieużywania (gwarantowane n * log (n)) stabilnego sortowania przez scalanie dla typów pierwotnych może być fakt, że wymaga to sklonowania tablicy. W przypadku typów referencyjnych, w których obiekty, do których odwołuje się odwołanie, zwykle zajmują znacznie więcej pamięci niż tablica odwołań, zazwyczaj nie ma to znaczenia. Ale w przypadku typów prymitywnych klonowanie tablicy bezpośrednio podwaja użycie pamięci.

Zgodnie z dokumentacją Java 7 API cytowaną w tej odpowiedzi , Arrays#Sort()tablice obiektów używają teraz TimSort , który jest hybrydą MergeSort i InsertionSort. Z drugiej strony, w Arrays#sort()przypadku tablic prymitywnych używa się teraz funkcji szybkiego sortowania Dual-Pivot . Te zmiany zostały wprowadzone począwszy od Java SE 7.

Jednym z powodów, które przychodzą mi do głowy, jest to, że quicksort ma najgorszą złożoność czasową O ( n ^ 2 ), podczas gdy łączenie zachowuje czas najgorszego przypadku O ( n log n ). W przypadku tablic obiektów istnieje uzasadnione oczekiwanie, że będzie wiele zduplikowanych odniesień do obiektów, co jest jednym z przypadków, w których szybkie sortowanie działa najgorzej.

Istnieje przyzwoite wizualne porównanie różnych algorytmów , zwróć szczególną uwagę na skrajny prawy wykres dla różnych algorytmów.

Brałem udział w zajęciach Coursera z Algorytmów iw jednym z wykładów profesor Bob Sedgewick wspominał o ocenie dla systemu Java sort:

„Jeśli programista używa obiektów, być może przestrzeń nie jest krytycznie ważnym czynnikiem, a dodatkowa przestrzeń używana przez sortowanie przez scalanie może nie stanowić problemu. A jeśli programista używa typów pierwotnych, być może najważniejsza jest wydajność, więc używają szybkie sortowanie."

java.util.Arrays używa quicksort dla typów pierwotnych, takich jak int i connectesort, dla obiektów, które implementują porównywalność lub używają komparatora . Pomysł użycia dwóch różnych metod polega na tym, że jeśli programista używa obiektów, być może przestrzeń nie jest krytycznie ważnym czynnikiem, a więc dodatkowa przestrzeń wykorzystywana przez łączenie może nie stanowi problemu, a jeśli programista używa typów prymitywnych, być może wydajność jest najważniejsza, więc użyj quicksort .

Na przykład: To jest przykład, gdy sortowanie ma znaczenie dla stabilności.

Dlatego stabilne sortowanie ma sens w przypadku typów obiektów, zwłaszcza typów obiektów z możliwością zmiany i typów obiektów zawierających więcej danych niż tylko klucz sortowania, a takim sortowaniem jest łączenie sortowania. Ale dla typów prymitywnych stabilność jest nie tylko nieistotna. To bez znaczenia.

Źródło: INFO

Arrays.sortMetoda Javy wykorzystuje szybkie sortowanie, sortowanie przez wstawianie i scalanie. W kodzie OpenJDK zaimplementowano nawet pojedyncze i podwójne szybkie sortowanie obrotowe. Najszybszy algorytm sortowania zależy od okoliczności, a zwycięzcami są: sortowanie przez wstawianie dla małych tablic (aktualnie wybranych 47), łączenie sortowania dla większości posortowanych tablic i szybkie sortowanie dla pozostałych tablic, więc Array.sort () języka Java próbuje wybrać najlepszy algorytm do mają zastosowanie w oparciu o te kryteria.