Co jest tańsze: posortować tablicę i potem wyszukać…

To zależy od kontekstu.

Pojedyncze wyszukiwanie w nieposortowanej tablicy:
- Posortować: Złożoność sortowania to zazwyczaj $O(n \log n)$ lub $O(n^2)$ (w zależności od algorytmu).
- Wyszukiwanie (binarne po sortowaniu): $O(\log n)$.
- Razem: $O(n \log n)$ lub $O(n^2)$.
- Przeszukiwanie liniowe (przeglądanie): $O(n)$.
- Razem: $O(n)$.
- W tym przypadku przeszukiwanie ($O(n)$) jest tańsze niż sortowanie + wyszukiwanie ($O(n \log n)$ lub więcej).
Wielokrotne wyszukiwania w tablicy:
- Jeśli trzeba wykonać $k$ wyszukiwań w tym samym arrayu.
- Posortować raz: $O(n \log n)$ lub $O(n^2)$.
- Wykonać $k$ wyszukiwań binarnych po sortowaniu: $k \times O(\log n) = O(k \log n)$.
- Razem: $O(n \log n + k \log n)$ lub $O(n^2 + k \log n)$.
- Wykonać $k$ przeszukiwań liniowych: $k \times O(n) = O(kn)$.
- Razem: $O(kn)$.
- Dla dużych $k$ ($k > \log n$), sortowanie z wyszukiwaniem binarnym staje się tańsze: $O(n \log n + k \log n)$ vs $O(kn)$.
Szczególne przypadki:
- Jeśli array jest już częściowo posortowany lub ma specjalną strukturę, istnieją szybsze algorytmy sortowania lub wyszukiwania.
- Tablice haszujące (Set lub Hash w Ruby) oferują średnio $O(1)$ czas wyszukiwania, co jest zwykle szybsze niż jakakolwiek metoda oparta na sortowaniu lub liniowym przeszukiwaniu.

Wniosek: Dla pojedynczego wyszukiwania przeszukiwanie jest tańsze. Dla wielu wyszukiwań w tym samym arrayu, sortowanie z wyszukiwaniem binarnym staje się bardziej opłacalne przy wystarczającej liczbie wyszukiwań. Jeśli szybkość wyszukiwania jest kluczowa, a struktura danych może być zmieniona, użycie Set lub Hash może być najbardziej optymalne.

Przykład liniowego wyszukiwania w Ruby:

# Wyszukiwanie elementu w nieposortowanej tablicy
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Zatrzymanie po znalezieniu pierwszego dopasowania
  end
end

puts found # => 8

Przykład sortowania i wyszukiwania binarnego w Ruby (z użyciem standardowych metod):

# Sortowanie
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) dla Timsort w Ruby

# Wyszukiwanie binarne (Ruby ma 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 "Element nie znaleziony"
end

Co jest tańsze: posortować tablicę i potem wyszukać, czy użyć przeszukiwania liniowego, aby znaleźć element?