2009-05-13 23 views
39

Cuando ordeno una matriz utilizando el método nativo sort, ¿qué algoritmo usa Ruby?¿Qué algoritmo usa el método de clasificación de Ruby?

¿Depende de los datos, es decir, si los datos son pequeños usa el algoritmo X sino que usa el algoritmo Y?

¿Es un tipo estable? ¿Cuál es la complejidad de tiempo promedio?

+0

La estabilidad del género de Ruby se trata en [esta pregunta] (https://stackoverflow.com/questions/15442298/is-sort-in-ruby-stable). –

Respuesta

25

vistazo aquí: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/

sí utiliza de forma nativa clasificación rápida sin embargo, que está n log n complejidad en promedio.

+2

Esto también significa que probablemente no sea un tipo estable. Consulte las explicaciones de esto en http://en.wikipedia.org/wiki/Quick_sort –

+0

Es cierto, especialmente si la matriz está casi ordenada, entonces la complejidad de la clasificación rápida se convierte en n^2. Aún así, es extremadamente rápido en la mayoría de los casos. – AlbertoPL

+1

Si la matriz está casi ordenada, solo una orden rápida estúpida va a n^2. La mediana de la selección de tres pivotes está en todas las implementaciones que he usado –

Cuestiones relacionadas