Perché il metodo Arrays.sort di Java utilizza due diversi algoritmi di ordinamento per tipi diversi?

Question

Il metodo Java Arrays.sort utilizza Quicksort per le matrici di primitive e unisce l'ordinamento per matrici di oggetti. Credo che la maggior parte del tempo Quicksort sia più veloce di unire l'ordinamento e costa meno memoria. I miei esperimenti supportano questo, sebbene entrambi gli algoritmi siano O (n log (n)). Quindi, perché sono utilizzati algoritmi diversi per tipi diversi?

Answer 1

Il motivo più probabile: quicksort non è stabile, ovvero voci uguali possono cambiare la loro posizione relativa durante l'ordinamento; tra le altre cose, questo significa che se si ordina una matrice già ordinata, potrebbe non rimanere invariata.

Poiché i tipi primitivi non hanno identità (non c'è modo di distinguere due inte con lo stesso valore), questo non ha importanza per loro. Ma per i tipi di riferimento, potrebbe causare problemi per alcune applicazioni. Pertanto, per questi viene utilizzato un ordinamento di unione stabile.

OTOH, un motivo per non utilizzare l'ordinamento di unione (garantito n * log (n)) per i tipi primitivi potrebbe essere che richiede un clone dell'array. Per i tipi di riferimento, in cui gli oggetti indicati occupano di solito molta più memoria rispetto alla matrice di riferimenti, generalmente questo non ha importanza. Ma per i tipi primitivi, la clonazione dell'array raddoppia l'utilizzo della memoria.

Answer 2

Uno dei motivi che posso pensare è che quicksort ha un peggiore complessità temporale nel caso di O (n^2 ) mentre mantiene Mergesort momento peggiore caso di O (n log n ). Per gli array di oggetti c'è una buona aspettativa che ci saranno più riferimenti a oggetti duplicati che è un caso in cui quicksort fa il peggio.

C'è un discreto visual comparison of various algorithms, prestare particolare attenzione al grafico più a destra per diversi algoritmi.

Answer 3

stavo prendendo classe Coursera su algoritmi e in una delle lezioni professor Bob Sedgewick citano la valutazione per il sistema Java sorta:

"Se un programmatore sta usando oggetti, forse lo spazio non è una critica importante considerazione e lo spazio extra utilizzato da un ordinamento di fusione forse non è un problema . E se un programmatore utilizza i tipi primitivi, forse le prestazioni sono la cosa più importante in modo da utilizzare l'ordinamento rapido. "

Answer 4

Secondo Java documenti 7 API citate this answer, Arrays#Sort() per array di oggetti utilizza ora TimSort, che è un ibrido di MergeSort e InsertionSort. D'altra parte, Arrays#sort() per gli array primitivi ora utilizza Dual-Pivot QuickSort. Queste modifiche sono state implementate a partire da Java SE 7.

Answer 5

Il metodo Java Arrays.sort utilizza quicksort, insertion sort e mergesort. C'è anche un quicksort pivot singolo e doppio implementato nel codice OpenJDK. L'algoritmo di ordinamento più veloce dipende dalle circostanze e i vincitori sono: ordinamento di inserzione per piccoli array (47 attualmente selezionati), mergesort per array in gran parte ordinati e quicksort per gli array restanti in modo che Array.sort() di Java cerchi di scegliere il miglior algoritmo per applicare in base a tali criteri.