heap sort

sort.rb

def left_child(parent)
  2 * parent + 1
end

def find_max_child_index(child, length, list)
  if child + 1 < length && list[child] < list[child + 1]
    child += 1
  end
  child
end

def sub_heap_adjust(length, list, max_child_index, parent, temp)

  if max_child_index >= length
    return parent
  end

  max_child_index = find_max_child_index(max_child_index, length, list)

  if temp >= list[max_child_index]
    return parent
  end

  list[parent] = list[max_child_index]

  sub_heap_adjust(length, list, left_child(parent), max_child_index, temp)

end

def heap_adjust(list, parent, length)

  old_parent_val = list[parent]

  max_child_index = left_child(parent)

  old_parent_to_index = sub_heap_adjust(length, list, max_child_index, parent, old_parent_val)

  list[old_parent_to_index] = old_parent_val

  list

end

def heap_sort(list)
  not_leaf_count = list.length / 2 - 1

  not_leaf_count.downto(0).each { |sub_tree_root_node|
    heap_adjust(list, sub_tree_root_node, list.length)
  }

  ((list.length - 1).downto(0)).each { |i|
    temp = list[0]
    list[0] = list[i]
    list[i] = temp

    heap_adjust(list, 0, i)
  }

  list

end


#####################
def less(list, i, j)
  list[i] < list[j]
end

def exchange(list, i, j)
  temp = list[i]
  list[i] = list[j]
  list[j] = temp
end

def swim(list, k)
  while k > 1 and less(list, k / 2, k)
    exchange(list, k / 2, k)
    k = k / 2
  end
end

def sink(list, k, len)
  while 2 * k <= len - 1
    j = 2 * k
    if j < len - 1 and less(list, j, (j + 1))
      j += 1
    end
    unless less(list, k, j)
      break
    end
    exchange(list, k, j)
    k = j
  end
end

def heap_sort_2(list)
  len = list.length

  k = len / 2
  while k >= 1
    sink(list, k, len)
    k -= 1
  end

  n = len - 1
  while n > 1
    exchange(list, 1, n)
    n -= 1
    sink(list, 1, n)
  end

  list

end