Dlaczego Collections.sort używa Mergesort, a Arrays.sort nie?

97

Używam JDK-8 (x64). W przypadku Arrays.sort(prymitywów) w dokumentacji Java znalazłem:

Algorytm sortowania to Dual-Pivot Quicksort autorstwa Vladimira Yaroslavskiya, Jona Bentleya i Joshua Blocha. "

Dla Collections.sort(obiektów) znalazłem to „Timsort”:

Ta implementacja jest stabilnym, adaptacyjnym, iteracyjnym łączeniem ... Ta implementacja zrzuca określoną listę do tablicy, sortuje tablicę i wykonuje iterację po liście resetując każdy element z odpowiedniej pozycji w tablicy.

Jeśli Collections.sortużywa tablicy, dlaczego po prostu nie wywołuje Arrays.sortlub nie używa funkcji QuickSort z dwoma obrotami ? Dlaczego warto korzystać z Mergesort ?

Quest Monger
źródło
9
To jest javadoc dla tablic prymitywów - tablice obiektów są sortowane przy użyciu meregsort.
asylias
2
connectesort daje u nlogn zawsze, podczas gdy quicksort może czasami dawać nlogn2 genally rozmiar tablic nie jest tak duży, ale kolekcje łatwo osiągają miliony wpisów, więc ryzyko nlogn2 nie jest warte PS nlogn2 miałem na myśli kwadrat n
Kumar Saurabh
O (n ^ 2) dla quicksort to skrajny najgorszy przypadek. W praktyce jest szybciej
James Wierzba
ale nie możesz ignorować tych caese podczas tworzenia api
Kumar Saurabh
2
Ten link jest bardzo powiązany.
qartal

Odpowiedzi:

100

API gwarantuje stabilne sortowanie, którego nie oferuje Quicksort . Jednak podczas sortowania wartości pierwotnych według ich naturalnej kolejności nie zauważysz różnicy, ponieważ wartości pierwotne nie mają tożsamości. Dlatego też Quicksort może być używany dla tablic pierwotnych i będzie używany, gdy zostanie uznany za bardziej wydajny¹ .

W przypadku obiektów można zauważyć, że obiekty o różnej tożsamości, które są uważane za równe w zależności od ich equalswykonania lub dostarczonej Comparatorzmiany, zmieniają kolejność. Dlatego Quicksort nie wchodzi w grę. Tak więc używany jest wariant MergeSort , obecne wersje Java używają TimSort . Dotyczy to obu Arrays.sorti Collections.sortchociaż w Javie 8 Listsamo w sobie może przesłonić algorytmy sortowania.


¹ Zaletą wydajności Quicksort jest to, że wymaga mniej pamięci, gdy jest wykonywana na miejscu. Ale ma dramatyczną wydajność w najgorszym przypadku i nie może wykorzystywać serii wstępnie posortowanych danych w tablicy, co robi TimSort .

Dlatego algorytmy sortowania zostały przerobione z wersji na wersję, pozostając w myląco nazwanej klasie DualPivotQuicksort. Ponadto dokumentacja nie nadrobiła zaległości, co pokazuje, że generalnie złym pomysłem jest nazwanie w specyfikacji algorytmu używanego wewnętrznie, gdy nie jest to konieczne.

Obecna sytuacja (w tym Java 8 do Java 11) przedstawia się następująco:

  • Ogólnie rzecz biorąc, metody sortowania tablic prymitywnych używają funkcji Quicksort tylko w określonych okolicznościach. W przypadku większych tablic będą najpierw próbować zidentyfikować serie wstępnie posortowanych danych, tak jak robi to TimSort , i scalą je, gdy liczba przebiegów nie przekroczy określonego progu. W przeciwnym razie powrócą do Quicksort , ale z implementacją, która powróci do sortowania przez wstawianie dla małych zakresów, co ma wpływ nie tylko na małe tablice, ale także na rekursję szybkiego sortowania.
  • sort(char[],…)i sort(short[],…)dodaj kolejny przypadek specjalny, aby użyć sortowania zliczającego dla tablic, których długość przekracza określony próg
  • Podobnie, sort(byte[],…)użyje sortowania zliczającego , ale ze znacznie mniejszym progiem, co tworzy największy kontrast w stosunku do dokumentacji, ponieważ sort(byte[],…)nigdy nie używa Quicksort. Używa sortowania przez wstawianie tylko dla małych tablic i sortowania zliczania w przeciwnym razie.
Holger
źródło
1
Hmm, co ciekawe, w pliku Javadoc Collections.sort jest napisane: „To sortowanie jest gwarantowane jako stabilne”, ale ponieważ deleguje do List.sort, co może być nadpisane przez implementacje list, stabilne sortowanie nie może być gwarantowane przez Kolekcje.sort dla całej listy wdrożenia. A może coś mi brakuje? List.sort nie wymaga, aby algorytm sortowania był stabilny.
Puce
11
@Puce: oznacza to po prostu, że odpowiedzialność za tę gwarancję spoczywa teraz na tych, którzy wdrażają List.sortmetodę nadrzędną . Collections.sortnigdy nie mógł zagwarantować poprawnego działania dla każdej Listimplementacji, ponieważ nie może zagwarantować, np. że Listnie zmienia ona błędnie swojej zawartości. Wszystko sprowadza się do tego, że gwarancja Collections.sortdotyczy tylko poprawnych Listimplementacji (i poprawnych Comparatorlub equalswdrożeń).
Holger
1
@Puce: Ale masz rację, Javadoc nie jest równie jednoznaczny co do tego ograniczenia w obu metodach, ale przynajmniej w najnowszej dokumentacji stwierdza się, że Collections.sortzostanie to delegowane List.sort.
Holger
@Puce: jest mnóstwo przykładów tego, w których ważne właściwości nie są częścią typu, ale raczej są wymienione w dokumentacji (a zatem nie są sprawdzane przez kompilator). System typów Javy jest po prostu zbyt słaby, aby wyrazić jakiekolwiek interesujące właściwości. (Pod tym względem nie różni się zbytnio od dynamicznie typowanego języka, tam również właściwości są zdefiniowane w dokumentacji i programista musi upewnić się, że nie są naruszane.) W rzeczywistości idzie jeszcze dalej: czy zauważyłeś który Collections.sortnawet nie wspomina w swoim sygnaturze typu, że dane wyjściowe są posortowane?
Jörg W Mittag
1
W języku z bardziej wyrazistym systemem typów zwracany typ Collections.sortbyłby czymś w rodzaju „kolekcji tego samego typu i długości co dane wejściowe, z właściwościami, że 1) każdy element obecny na wejściu jest również obecny w danych wyjściowych, 2 ) dla każdej pary elementów z wyjścia lewy jest nie większy niż prawy, 3) dla każdej pary równych elementów z wyjścia, lewy indeks na wejściu jest mniejszy niż prawy "lub coś podobnego że.
Jörg W Mittag
20

Nie znam dokumentacji, ale implementacja java.util.Collections#sortw Javie 8 (HotSpot) wygląda tak:

@SuppressWarnings({"unchecked", "rawtypes"})
public static <T> void sort(List<T> list, Comparator<? super T> c) {
    list.sort(c);
}

I List#sortma tę implementację:

@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

W końcu Collections#sort używa Arrays#sort(elementów obiektów) za kulisami. Ta implementacja używa sortowania przez scalanie lub sortowania według czasu.

Luiggi Mendoza
źródło
16

Według Javadoc tylko prymitywne tablice są sortowane za pomocą Quicksort. Tablice obiektów są również sortowane za pomocą Mergesort.

Wydaje się więc, że Collections.sort używa tego samego algorytmu sortowania, co Arrays.sort dla obiektów.

Innym pytaniem byłoby, dlaczego inny algorytm sortowania jest używany dla tablic pierwotnych niż dla tablic Object?

Kolor brązowofioletowy
źródło
2

Jak stwierdzono w wielu odpowiedziach.

Funkcja Quicksort jest używana przez Arrays.sort do sortowania kolekcji pierwotnych, ponieważ stabilność nie jest wymagana (nie będziesz wiedzieć lub przejmować się tym, czy podczas sortowania zamieniono dwa identyczne liczby całkowite)

MergeSort, a dokładniej Timsort, jest używany przez Arrays.sort do sortowania kolekcji obiektów. Wymagana jest stabilność. Quicksort nie zapewnia stabilności, Timsort tak.

Collections.sort deleguje do Arrays.sort, dlatego widzisz javadoc odwołujący się do MergeSort.

cogitoboy
źródło
1

Szybkie sortowanie ma dwie główne wady, jeśli chodzi o sortowanie przez scalanie:

  • Nie jest stabilny, jeśli chodzi o nieprymitywne.
  • Nie gwarantuje wydajności n log n.

Stabilność nie jest problemem dla typów pierwotnych, ponieważ nie istnieje pojęcie tożsamości jako odrębnej od równości (wartości).

Stabilność to poważna sprawa podczas sortowania dowolnych obiektów. Dodatkową zaletą jest to, że sortowanie przez scalanie gwarantuje wydajność n log n (czas) bez względu na dane wejściowe. Dlatego wybrano sortowanie przez scalanie, aby zapewnić stabilne sortowanie (sortowanie przez scalanie) do sortowania odniesień do obiektów.

Krutik
źródło
1
Co masz na myśli mówiąc „niestabilny”?
Arun Gowda