Por que Collections.sort usa Mergesort, mas Arrays.sort não?

94

Estou usando o JDK-8 (x64). Para Arrays.sort(primitivos), encontrei o seguinte na documentação do Java:

O algoritmo de classificação é um Quicksort Dual-Pivot de Vladimir Yaroslavskiy, Jon Bentley e Joshua Bloch.

Para Collections.sort(objetos), encontrei este "Timsort":

Esta implementação é um mergesort estável, adaptável e iterativo ... Esta implementação despeja a lista especificada em uma matriz, classifica a matriz e itera sobre a lista, redefinindo cada elemento da posição correspondente na matriz.

Se Collections.sortusa uma matriz, por que simplesmente não chama Arrays.sortou usa QuickSort dual-pivot ? Por que usar Mergesort ?

Quest Monger
fonte
8
Esse é o javadoc para arrays de primitivos - arrays de objetos são classificados usando meregsort.
Assylias 01 de
2
mergesort dá u nlogn sempre enquanto quicksort pode às vezes dar ao nlogn2 o tamanho dos arrays genealógicos não é tão grande, mas as coleções facilmente sobem para milhões de entradas, então correr o risco de nlogn2 não vale PS nlogn2 i significa sqaure de n
Kumar Saurabh
O (n ^ 2) para quicksort é o pior caso extremo. Na prática, é mais rápido
James Wierzba,
mas você não pode ignorar esses caese enquanto faz uma api
Kumar Saurabh
2
Este link está muito relacionado.
qartal de

Respostas:

99

A API garante uma classificação estável que Quicksort não oferece. No entanto, ao classificar os valores primitivos por sua ordem natural, você não notará a diferença, pois os valores primitivos não têm identidade. Portanto, Quicksort pode ser usado para arrays primitivos e será usado quando for considerado mais eficiente¹.

Para objetos, você pode notar, quando objetos com identidade diferente que são considerados iguais de acordo com sua equalsimplementação ou o fornecido Comparatormudam sua ordem. Portanto, Quicksort não é uma opção. Portanto, uma variante de MergeSort é usada, as versões atuais do Java usam TimSort . Isso se aplica a ambos Arrays.sorte Collections.sort, embora com Java 8, o Listpróprio pode substituir os algoritmos de classificação.


¹ A vantagem de eficiência do Quicksort é a necessidade de menos memória quando feito no local. Mas tem um desempenho dramático no pior caso e não pode explorar execuções de dados pré-classificados em um array, o que o TimSort faz.

Portanto, os algoritmos de classificação foram retrabalhados de versão para versão, enquanto permaneciam na classe agora erroneamente nomeada DualPivotQuicksort. Além disso, a documentação não alcançou o atraso, o que mostra que é uma má ideia em geral, nomear um algoritmo usado internamente em uma especificação, quando não necessário.

A situação atual (incluindo Java 8 a Java 11) é a seguinte:

  • Geralmente, os métodos de classificação para matrizes primitivas usarão Quicksort somente em certas circunstâncias. Para matrizes maiores, eles tentarão identificar as execuções de dados pré-classificados primeiro, como o TimSort faz, e os mesclarão quando o número de execuções não exceder um determinado limite. Caso contrário, eles recorrerão ao Quicksort , mas com uma implementação que retornará à classificação por inserção para intervalos pequenos, o que não afeta apenas pequenos arrays, mas também a recursão da classificação rápida.
  • sort(char[],…)e sort(short[],…)adicionar outro caso especial, para usar a classificação por contagem para matrizes cujo comprimento excede um certo limite
  • Da mesma forma, sort(byte[],…)usará a classificação por contagem , mas com um limite muito menor, o que cria o maior contraste com a documentação, já que sort(byte[],…)nunca usa Quicksort. Ele só usa a classificação por inserção para pequenos arrays e, caso contrário, a classificação por contagem .
Holger
fonte
1
Hmm, curiosamente, o Javadoc Collections.sort afirma: "Esta classificação é garantida como estável", mas como delega a List.sort, que pode ser substituída por implementações de lista, a classificação estável não pode realmente ser garantida por Collections.sort para todas as listas implementações. Ou eu sinto falta de alguma coisa? E List.sort não exige que o alogirthm de classificação seja estável.
Puce
11
@Puce: isso significa simplesmente que a responsabilidade por essa garantia agora está nas mãos daqueles que implementam o List.sortmétodo de substituição . Collections.sortnunca poderia garantir o funcionamento correto para cada Listimplementação, uma vez que não pode garantir, por exemplo, que o Listnão altera seu conteúdo de forma espúria. Tudo se resume a que a garantia de Collections.sortapenas se aplica a Listimplementações corretas (e corretas Comparatorou equalsimplementações).
Holger
1
@Puce: Mas você está certo, o Javadoc não é igualmente explícito sobre essa restrição em ambos os métodos. Mas pelo menos a documentação mais recente afirma que Collections.sortirá delegar para List.sort.
Holger
@Puce: existem vários exemplos disso, onde propriedades importantes não fazem parte do tipo, mas apenas mencionadas na documentação (e, portanto, não verificadas pelo compilador). O sistema de tipos do Java é simplesmente muito fraco para expressar quaisquer propriedades interessantes. (Não é muito diferente de uma linguagem digitada dinamicamente a esse respeito, lá também as propriedades são definidas na documentação e cabe ao programador certificar-se de que não sejam violadas.) Na verdade, vai ainda mais longe: você percebeu que Collections.sortnem mesmo menciona em sua assinatura de tipo que a saída está classificada?
Jörg W Mittag
1
Em uma linguagem com um sistema de tipos mais expressivo, o tipo de retorno de Collections.sortseria algo como "uma coleção do mesmo tipo e comprimento da entrada com as propriedades que 1) cada elemento presente na entrada também está presente na saída, 2 ) para cada par de elementos da saída, o esquerdo não é maior que o direito, 3) para cada par de elementos iguais da saída, o índice do esquerdo na entrada é menor que o direito "ou algo como aquele.
Jörg W Mittag
20

Não sei sobre a documentação, mas a implementação do java.util.Collections#sortem Java 8 (HotSpot) é assim:

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

E List#sorttem esta implementação:

@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);
    }
}

Então, no final, Collections#sortusa Arrays#sort(de elementos de objeto) nos bastidores. Esta implementação usa merge sort ou tim sort.

Luiggi Mendoza
fonte
16

De acordo com o Javadoc, apenas arrays primitivos são classificados usando Quicksort. Matrizes de objetos são classificadas com um Mergesort também.

Portanto, Collections.sort parece usar o mesmo algoritmo de classificação que Arrays.sort para Objetos.

Outra questão seria por que um algoritmo de classificação diferente é usado para matrizes primitivas e não para matrizes de objetos?

Puce
fonte
2

Conforme afirmado em muitas das respostas.

O Quicksort é usado por Arrays.sort para classificar coleções primitivas porque a estabilidade não é necessária (você não saberá ou se importará se dois ints idênticos foram trocados na classificação)

MergeSort ou mais especificamente Timsort é usado por Arrays.sort para classificar coleções de objetos. A estabilidade é necessária. O Quicksort não oferece estabilidade, mas o Timsort.

Collection.sort delega para Arrays.sort, razão pela qual você vê o javadoc referenciando o MergeSort.

cogitoboy
fonte
1

A classificação rápida tem duas desvantagens principais quando se trata de classificação por mesclagem:

  • Não é estável enquanto se trata de não primitivo.
  • Não garante desempenho n log n.

A estabilidade não é um problema para os tipos primitivos, pois não há noção de identidade distinta da igualdade (de valor).

A estabilidade é um grande problema ao classificar objetos arbitrários. É um bom benefício colateral que Merge Sort garante desempenho n log n (tempo), independentemente da entrada. É por isso que merge sort é selecionado para fornecer uma ordenação estável (Merge Sort) para ordenar referências de objetos.

Krutik
fonte
1
O que quer dizer "Não estável"?
Arun Gowda