public
Last active

heap sort

  • Download Gist
sort.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.