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

121

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?

zjffdu
źródło
14
Najgorszym przypadkiem Quicksort jest N ^ 2, a nie NlogN.
codaddict
Czekaj, co się stanie, jeśli masz tablicę Integers czy coś?
Tikhon Jelvis
1
Czy nie jest to wyjaśnione w źródle, które czytasz?
Humphrey Bogart,
5
Ta informacja nie jest już aktualna. Począwszy od Java SE 7, MergeSort został zastąpiony przez TimSort, a QuickSort został zastąpiony przez Dual-Pivot QuickSort . Zobacz moją odpowiedź poniżej, aby uzyskać linki do dokumentacji Java API.
Will Byrne

Odpowiedzi:

200

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.

Michael Borgwardt
źródło
1
Innym powodem używania quicksort jest to, że w przeciętnym przypadku quicksort jest szybsze niż connectesort. Chociaż quicksort robi więcej porównań niż meresort, robi znacznie mniej dostępu do tablicy. 3-drożne szybkie sortowanie może również osiągnąć liniowy czas, jeśli wejście zawiera wiele zduplikowanych wpisów, co nie jest niczym niezwykłym w praktycznych zastosowaniach (przypuszczam, że szybkie sortowanie z podwójnym obrotem również ma tę właściwość).
Jingguo Yao,
W przypadku typów prymitywnych nie klonuje tablicy, może je sortować w miejscu, więc myślę, że jedynym powodem jest umowa stabilności, w zasadzie ...
rogerdpack
27

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.

Will Byrne
źródło
2
To nie jest odpowiedź, dlaczego wybrano 2 różne algorytmy.
Alexandr
12

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.

msw
źródło
2
Java quicksort to zmodyfikowany quicksort, który nie zmienia się w O (n ^ 2), z dokumentów "Ten algorytm oferuje wydajność n * log (n) na wielu zestawach danych, co powoduje, że inne szybkie sortowanie degradują się do wydajności kwadratowej"
pomija
7

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."

kukido
źródło
4
To nie jest główny powód. Zaraz po tym zdaniu pojawiło się pytanie, osadzone w filmie o „Dlaczego w przypadku typów referencyjnych zastosowano MergeSort?” (ponieważ jest stabilny). Myślę, że Sedgewick nie wspomniał o tym w filmie, aby zostawić to na pytanie.
podobnie jak
1

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.

wprowadź opis obrazu tutaj

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

Dinesh Kumar
źródło
0

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.

David McManamon
źródło