Skip to content

@lysu /sort.rb
Last active

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
heap sort
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.