Quando ordino una matrice usando il metodo nativo sort, quale algoritmo utilizza Ruby?Quale algoritmo utilizza il metodo di ordinamento di Ruby?
È dipendente dai dati, vale a dire se i dati sono piccoli, utilizza l'algoritmo X altrimenti utilizza l'algoritmo Y?
È un ordinamento stabile? Qual è la complessità temporale media?
un'occhiata qui: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/
Non nativamente usa quicksort tuttavia, che è n log n complessità in media.
Ciò significa anche che molto probabilmente non è un ordinamento stabile. Vedere le spiegazioni di questo a http://en.wikipedia.org/wiki/Quick_sort –
Vero, soprattutto se la matrice è quasi ordinata, quindi la complessità dell'ordinamento veloce diventa n^2. Tuttavia, è estremamente veloce nella maggior parte dei casi. – AlbertoPL
Se la matrice è quasi ordinata, solo uno stupido quicksort va a n^2. La selezione mediana di tre pivot è in tutte le implementazioni che ho usato –
La stabilità di Ruby è risolta in [questa domanda] (https://stackoverflow.com/questions/15442298/is-sort-in-ruby-stable). –