vegetables

0_vegetables.rb

#apparently the gist 'title' is just the name of the lexicographically first filename 

insertion_sort.rb

def isort(arr)
  for i in 1...arr.length
    j = i
    while j > 0 && arr[j-1] > arr[j]
      arr[j-1], arr[j] = arr[j], arr[j-1]
      j -= 1
    end
  end
  arr
end

merge_sort.rb

def merge_sort(arr)
  len = arr.length
  if len <=1
    return arr
  else
    left = merge_sort(arr[0...len/2])
    right = merge_sort(arr[len/2...len])
  end

  merge(left, right)
end

def merge(arr1, arr2)
  merged = []
  while arr1.length > 0 && arr2.length > 0
    if arr1[0] <= arr2[0]
      merged << arr1.shift
    else
      merged << arr2.shift
    end
  end
  merged + arr1 + arr2
end

quicksort.rb

def quicksort(arr, low=0, high=arr.length-1)
  if low < high
    p = partition(arr, low, high) 
    quicksort(arr, low, p-1)
    quicksort(arr, p+1, high)
  else
    return arr
  end
end

# better for non-random inputs
def partition(arr, low, high)
  #pick a random elment to be the pivot, much better for already-sorted arrays
  random_index = low + rand(high-low)
  arr[low], arr[random_index] = arr[random_index], arr[low]

  pivot_el = arr[low]

  i = low
  j = high + 1

  while true
    i += 1
    while i <= high && arr[i] < pivot_el
      i += 1
    end
    j -= 1
    while arr[j] > pivot_el
      j -= 1
    end
    break if i > j
    arr[i], arr[j] = arr[j], arr[i]
  end
  arr[low], arr[j] = arr[j], arr[low]
  j
end

#simplest quicksort
#leftmost element as initial pivot == worst case scenerio for already sorted arrays
def partition(arr, low, high)
  pivot_el = arr[low]
  m = low

  for i in low+1..high
    if arr[i] < pivot_el
      m += 1
      arr[m], arr[i] = arr[i], arr[m]
    end
  end
  arr[m], arr[low] = arr[low], arr[m]
  m
end

string_key_hash_table.rb

class StringKeyHashTable
  attr_reader :num_buckets, :values

  def initialize(num_buckets = 31)
    @values = Array.new(num_buckets)
    @num_buckets = num_buckets
  end

  def hash_func(str)
    str.each_char.with_index.inject(0) do |sum, (char, i)|
      sum += char.downcase.ord * i
    end % num_buckets
  end

  def add(key, value)
    hashed_index = hash_func(key)
    values[hashed_index] = HashTableEntry.new(
      key,
      value,
      values[hashed_index]
    )
  end

  def get(key)
    hashed_index = hash_func(key)
    maybe_entry = values[hashed_index]
    while true
      if maybe_entry.unhashed_key == key
        return maybe_entry.value
      else
        maybe_entry = maybe_entry.next_val
      end
      break if maybe_entry.nil?
    end
  end


  class HashTableEntry
    attr_reader :unhashed_key, :value, :next_val

    def initialize(unhashed_key, value, next_val)
      @unhashed_key = unhashed_key
      @value = value
      @next_val = next_val
    end
  end
end