Instantly share code, notes, and snippets.

# lysu/sort.rb Last active Dec 15, 2015

What would you like to do?
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