Когда я сортирую массив, используя собственный метод sort, какой алгоритм использует Ruby?Какой алгоритм использует метод сортировки Ruby?
Является ли оно зависимым от данных, то есть если данные малы, то он использует алгоритм X, иначе он использует алгоритм Y?
Это стабильный вид? Какова средняя временная сложность?
Посмотрите здесь: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/
Это естественным образом использовать быструю сортировку, однако, который п журнал п сложности в среднем.
Это также означает, что это, скорее всего, не стабильный вид. См. Объяснения этого на http://en.wikipedia.org/wiki/Quick_sort –
Правда, особенно если массив почти отсортирован, то сложность быстрой сортировки становится n^2. Тем не менее, в большинстве случаев это очень быстро. – AlbertoPL
Если массив почти отсортирован, только глупая quicksort переходит к n^2. Медиана из трех точек поворота - во всех реализациях, которые я использовал –
Стабильность вида Ruby адресуется в [этот вопрос] (https://stackoverflow.com/questions/15442298/is-sort-in-ruby-stable). –