Mi kerül kevesebbe: rendezni egy tömböt, majd…

A kontextustól függ.

Egyszeri keresés nem rendezett tömbben:
- Rendezés: A rendezés összetettsége általában $O(n \log n)$ vagy $O(n^2)$ (az algoritmustól függően).
- Keresés (bináris a rendezés után): $O(\log n)$.
- Összesen: $O(n \log n)$ vagy $O(n^2)$.
- Lineáris keresés (sorozat): $O(n)$.
- Összesen: $O(n)$.
- Ebben az esetben a sorozat ($O(n)$) olcsóbb, mint a rendezés + keresés ($O(n \log n)$ vagy több).
Többszöri keresés ugyanabban a tömbben:
- Ha $k$ keresést kell végrehajtani ugyanabban a tömbben.
- Egy alkalommal rendezés: $O(n \log n)$ vagy $O(n^2)$.
- $k$ bináris keresés a rendezés után: $k \times O(\log n) = O(k \log n)$.
- Összesen: $O(n \log n + k \log n)$ vagy $O(n^2 + k \log n)$.
- $k$ lineáris átvizsgálás: $k \times O(n) = O(kn)$.
- Összesen: $O(kn)$.
- Nagy $k$ esetén ($k > \log n$), a rendezés bináris kereséssel olcsóbb: $O(n \log n + k \log n)$ szemben $O(kn)$.
Különleges esetek:
- Ha a tömb már részben rendezett vagy speciális struktúrával rendelkezik, gyorsabb rendezési vagy keresési algoritmusok léteznek.
- Hash-táblák (Set vagy Hash Ruby-ben) átlagosan $O(1)$ időt kínálnak a kereséshez, ami általában gyorsabb, mint bármilyen rendezésen vagy lineáris keresésen alapuló módszer.

Következtetés: Egyedi keresés esetén a sorozat olcsóbb. Többszöri keresés ugyanabban a tömbben a rendezés és bináris keresés hatékonyabb, ha a keresések száma elég nagy. Ha a keresés gyorsasága kritikus, és az adatszerkezet módosítható, a Set vagy Hash használata lehet a legoptimálisabb megoldás.

Ruby példája lineáris keresésnek:

# Egy elem keresése nem rendezett tömbben
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Az első egyezés megtalálása után megáll
  end
end

puts found # => 8

Ruby példája rendezés és bináris keresésnek (alapértelmezett módszerek használatával):

# Rendezés
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) Ruby-ben Timsort

# Bináris keresés (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 "Elem nem található"
end

Mi kerül kevesebbe: rendezni egy tömböt, majd keresni, vagy végigmenni a tömbön egy elem keresése érdekében?