Qu'est-ce qui est moins cher : trier un tableau puis…

Cela dépend du contexte.

Recherche unique dans un tableau non trié :
- Trier : La complexité du tri est généralement $O(n \log n)$ ou $O(n^2)$ (selon l'algorithme).
- Recherche (binaire après tri) : $O(\log n)$.
- Total : $O(n \log n)$ ou $O(n^2)$.
- Parcours (recherche linéaire) : $O(n)$.
- Total : $O(n)$.
- Dans ce cas, parcourir ($O(n)$) est moins cher que trier + rechercher ($O(n \log n)$ ou plus).
Recherche multiple dans un tableau :
- Si vous devez effectuer $k$ recherches dans le même tableau.
- Trier une fois : $O(n \log n)$ ou $O(n^2)$.
- Effectuer $k$ recherches binaires après tri : $k \times O(\log n) = O(k \log n)$.
- Total : $O(n \log n + k \log n)$ ou $O(n^2 + k \log n)$.
- Effectuer $k$ parcours linéaires : $k \times O(n) = O(kn)$.
- Total : $O(kn)$.
- Pour de grands $k$ ($k > \log n$), le tri avec recherche binaire devient plus économique : $O(n \log n + k \log n)$ contre $O(kn)$.
Cas particuliers :
- Si le tableau est déjà partiellement trié ou possède une structure particulière, il existe des algorithmes de tri ou de recherche plus rapides.
- Les tables de hachage (Set ou Hash en Ruby) offrent en moyenne $O(1)$ de temps pour la recherche, ce qui est généralement plus rapide que toute méthode basée sur le tri ou la recherche linéaire.

Conclusion : La recherche unique par parcours est moins coûteuse. Pour plusieurs recherches dans le même tableau, le tri avec recherche binaire devient plus avantageux avec un nombre suffisant de recherches. Si la vitesse de recherche est cruciale et que la structure de données peut être modifiée, l'utilisation de Set ou Hash peut être la solution la plus optimale.

Exemple de recherche linéaire en Ruby :

# Recherche d'un élément dans un tableau non trié
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Arrêt après la première correspondance
  end
end

puts found # => 8

Exemple de tri et recherche binaire en Ruby (avec méthodes standard) :

# Tri
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n log n) pour Timsort en Ruby

# Recherche binaire (Ruby a bsearch)
target = 8
index = sorted_array.bsearch_index { |x| x >= target } # O(log n)

if index && sorted_array[index] == target
  puts sorted_array[index] # => 8
else
  puts "Élément non trouvé"
end

Qu'est-ce qui est moins cher : trier un tableau puis effectuer une recherche, ou utiliser une recherche par parcours pour trouver un élément?