Wat is goedkoper: een array sorteren en vervolgens…

Het hangt af van de context.

Eén enkele zoekopdracht in een niet-gesorteerde array:
- Sorteren: De complexiteit van sorteren is meestal $O(n \log n)$ of $O(n^2)$ (afhankelijk van het algoritme).
- Zoeken (binair na sortering): $O(\log n)$.
- Totaal: $O(n \log n)$ of $O(n^2)$.
- Lineair doorzoeken (lineaire zoekopdracht): $O(n)$.
- Totaal: $O(n)$.
- In dit geval is doorzoeken ($O(n)$) goedkoper dan sorteren + zoeken ($O(n \log n)$ of meer).
Meerdere zoekopdrachten in één array:
- Als je $k$ zoekopdrachten in dezelfde array moet uitvoeren.
- Eén keer sorteren: $O(n \log n)$ of $O(n^2)$.
- $k$ keer binair zoeken na sortering: $k \times O(\log n) = O(k \log n)$.
- Totaal: $O(n \log n + k \log n)$ of $O(n^2 + k \log n)$.
- $k$ keer lineair doorzoeken: $k \times O(n) = O(kn)$.
- Totaal: $O(kn)$.
- Voor grote $k$ ($k > \log n$) wordt sorteren met binair zoeken goedkoper: $O(n \log n + k \log n)$ versus $O(kn)$.
Speciale gevallen:
- Als de array al gedeeltelijk gesorteerd is of een speciale structuur heeft, zijn er snellere sorteermethoden of zoekalgoritmen.
- Hash-tabellen (Set of Hash in Ruby) bieden gemiddeld $O(1)$ tijd voor zoeken, wat meestal sneller is dan elke methode gebaseerd op sorteren of lineair zoeken.

Conclusie: Voor één enkele zoekopdracht is doorzoeken goedkoper. Voor meerdere zoekopdrachten in dezelfde array wordt sorteren met binair zoeken efficiënter bij voldoende aantal zoekopdrachten. Als de zoekingssnelheid cruciaal is en de datastructuur kan worden aangepast, is het gebruik van Set of Hash de meest optimale oplossing.

Voorbeeld van lineair zoeken in Ruby:

# Zoek een element in een niet-gesorteerde array
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Stop na het vinden van de eerste match
  end
end

puts found # => 8

Voorbeeld van sorteren en binair zoeken in Ruby (met standaardmethoden):

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

# Binair zoeken (Ruby heeft 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 niet gevonden"
end

Wat is goedkoper: een array sorteren en vervolgens zoeken, of een doorloop gebruiken om een element te vinden?