L'algorithme n'Ruby est une sorte de méthode utiliser?

Quand je trie un Tableau en utilisant le natif sort méthode, l'algorithme ne Rubis utiliser?

Est-il des données à charge, c'est à dire, si les données est petit il utilise X algorithme d'autre il Y utilise l'algorithme?

Est-il un tri stable? Quelle est la durée moyenne de la complexité?

  • La stabilité de Ruby est un genre est abordé dans le cette question.
InformationsquelleAutor unj2 | 2009-05-13
  1. 27

    Regardez ici: http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/

    Il ne nativement utilisation quicksort cependant, ce qui est n log n de la complexité en moyenne.

    • Cela signifie aussi qu'il n'est probablement pas un tri stable. Voir les explications de ce en.wikipedia.org/wiki/Quick_sort
    • Vrai, surtout si le tableau est presque triées, puis tri rapide de la complexité devient n^2. Pourtant, il est extrêmement rapide dans la plupart des cas.
    • Si le tableau est presque triées, seulement stupide quicksort va à n^2. La médiane de trois pivot de la sélection est dans tous les implementattions j'ai utilisé
    • Eggermont: autant Que je sache, aussi médiane de trois pivot est n^2 dans le pire des cas.
    • Pas pour presque un tableau trié, qui est près de pire des cas pour un stupide pivot de la sélection (premier élément)
    • Je me demande si le mot "stupide" est en fait un mot technique pour la description de ces algorithmes
    • Le terme technique pour "stupide" est "naïf".

    InformationsquelleAutor AlbertoPL