Cosa è più economico: ordinare un array e poi…

Dipende dal contesto.

Ricerca singola in un array non ordinato:
- Ordinare: La complessità di ordinamento è generalmente $O(n \log n)$ o $O(n^2)$ (dipende dall'algoritmo).
- Ricerca (binaria dopo ordinamento): $O(\log n)$.
- Totale: $O(n \log n)$ o $O(n^2)$.
- Ricerca lineare (percorso): $O(n)$.
- Totale: $O(n)$.
- In questo caso, il percorso ($O(n)$) è più economico rispetto all'ordinamento + ricerca ($O(n \log n)$ o peggio).
Ricerca multipla in un array:
- Se devi eseguire $k$ ricerche nello stesso array.
- Ordinare una volta: $O(n \log n)$ o $O(n^2)$.
- Eseguire $k$ ricerche binarie dopo l'ordinamento: $k \times O(\log n) = O(k \log n)$.
- Totale: $O(n \log n + k \log n)$ o $O(n^2 + k \log n)$.
- Eseguire $k$ percorrenze lineari: $k \times O(n) = O(kn)$.
- Totale: $O(kn)$.
- Per grandi $k$ ($k > \log n$), l'ordinamento con ricerca binaria diventa più economico: $O(n \log n + k \log n)$ contro $O(kn)$.
Casi particolari:
- Se l'array è già parzialmente ordinato o ha una struttura speciale, esistono algoritmi di ordinamento o ricerca più veloci.
- Le tabelle hash (Set o Hash in Ruby) offrono in media $O(1)$ tempo per la ricerca, che di solito è più veloce di qualsiasi metodo basato su ordinamento o ricerca lineare.

Conclusione: Per una singola ricerca, la percorrenza è più economica. Per ricerche multiple nello stesso array, l'ordinamento con ricerca binaria diventa più efficiente con un numero sufficiente di ricerche. Se la velocità di ricerca è critica e la struttura dei dati può essere modificata, l'uso di Set o Hash può essere la soluzione più ottimale.

Esempio di ricerca lineare in Ruby:

# Ricerca di un elemento in un array non ordinato
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Fermarsi dopo aver trovato la prima corrispondenza
  end
end

puts found # => 8

Esempio di ordinamento e ricerca binaria in Ruby (usando metodi standard):

# Ordinamento
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) per Timsort in Ruby

# Ricerca binaria (Ruby ha 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 "Elemento non trovato"
end

Cosa è più economico: ordinare un array e poi cercare, o usare una ricerca lineare per trovare un elemento?