Šta je jeftinije: sortirati niz i zatim tražiti, ili…

Зависи од контекста.

Једнократно претраживање у несортираном низу:
- Сортирање: Време сортирања обично је $O(n \log n)$ или $O(n^2)$ (зависи од алгоритма).
- Претраживање (бинарно након сортирања): $O(\log n)$.
- Укупно: $O(n \log n)$ или $O(n^2)$.
- Претрага (линеарна претрага): $O(n)$.
- Укупно: $O(n)$.
- У овом случају претрага ($O(n)$) је јефтинија од сортирања + претраге ($O(n \log n)$ или више).
Многократно претраживање у низу:
- Ако је потребно извршити $k$ претрага у истом низу.
- Једном сортирање: $O(n \log n)$ или $O(n^2)$.
- Извршити $k$ бинарних претрага након сортирања: $k \times O(\log n) = O(k \log n)$.
- Укупно: $O(n \log n + k \log n)$ или $O(n^2 + k \log n)$.
- Извршити $k$ линеарних претрага: $k \times O(n) = O(kn)$.
- Укупно: $O(kn)$.
- За велика $k$ ($k > \log n$), сортирање са бинарном претрагом постаје исплативије: $O(n \log n + k \log n)$ у односу на $O(kn)$.
Посебни случајеви:
- Ако је низ већ делимично сортиран или има посебну структуру, постоје бржи алгоритми за сортирање или претрагу.
- Хеш-табеле (Set или Hash у Ruby-ју) у просеку пружају $O(1)$ време за претрагу, што је обично брже од било које методе засноване на сортирању или линеарној претрази.

Закључак: За једноставно претраживање, претрага је јефтинија. За многократно претраживање у истом низу, сортирање са бинарном претрагом постаје исплативије при довољно великом броју претрага. Ако је брзина претраге важна и структура података може бити измењена, коришћење Set или Hash може бити најоптималније решење.

Пример линеарне претраге у Ruby-ју:

# Претрага елемента у несортираном низу
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Остановка након проналаска првог поклапања
  end
end

puts found # => 8

Пример сортирања и бинарне претраге у Ruby-ју (са коришћењем стандардних метода):

# Сортирање
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # $O(n \log n)$ за Timsort у Ruby-ју

# Бинарна претрага (Ruby има уграђени 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 "Елемент није пронађен"
end

Šta je jeftinije: sortirati niz i zatim tražiti, ili koristiti pretraživanje za pronalaženje elementa?