search_algorithms.rb

class Array
  def sequential_search(element)
    each do |e|
      return e if e == element
    end

    nil
  end

  def binary_search(element)
    index = 0
    distance = self.count
    found_index = nil

    while (index <= distance)
      found_index = (index + distance) / 2
      return found_index if self[found_index] == element

      if (self[found_index] < element)
        index = found_index + 1
      else
        distance = found_index - 1
      end
    end

    return nil
  end

  def bubble_sort
    external_counter  = internal_counter = 0
    temporary_element = nil

    for external_counter in 0...self.count
      for internal_counter in (external_counter+1)...self.count
        if self[internal_counter] < self[external_counter]
          temporary_element = self[internal_counter]
          self[internal_counter] = self[external_counter]
          self[external_counter] = temporary_element
        end
      end
    end

    self
  end

  def merge_sort
    @tempory_array = Array.new(self.size)
    do_merge_sort(0, self.size - 1)
    self
  end

  private

  def do_merge_sort(lower_index, higher_index)
    if (lower_index < higher_index)
      middle_index = lower_index + (higher_index - lower_index) / 2
      do_merge_sort(lower_index, middle_index)
      do_merge_sort(middle_index+1, higher_index)
      merge_parts(lower_index, middle_index, higher_index)
    end
  end

  def merge_parts(lower_index, middle_index, higher_index)
    for i in lower_index..higher_index
      @tempory_array[i] = self[i]
    end

    i = lower_index
    j = middle_index + 1
    k = lower_index

    while (i <= middle_index && j <= higher_index)
      if(@tempory_array[i] <= @tempory_array[j])
        self[k] = @tempory_array[i]
        i+=1
      else
        self[k] = @tempory_array[j]
        j+=1
      end
      k+=1
    end

    while(i <= middle_index)
      self[k] = @tempory_array[i]
      k+=1
      i+=1
    end
  end
end