Skip to content

Instantly share code, notes, and snippets.

@Shikugawa
Created December 25, 2018 08:25
Show Gist options
  • Save Shikugawa/d800073de15dd05ad495a9e72cbc6f27 to your computer and use it in GitHub Desktop.
Save Shikugawa/d800073de15dd05ad495a9e72cbc6f27 to your computer and use it in GitHub Desktop.
ソート
def merge(left, right)
merged = []
first_index = 0
second_index = 0
while first_index < left.length || second_index < right.length
if first_index == left.length
merged << right[second_index]
second_index += 1
next
end
if second_index == right.length
merged << left[first_index]
first_index += 1
next
end
if left[first_index] > right[second_index]
merged << right[second_index]
second_index += 1
else
merged << left[first_index]
first_index += 1
end
end
return merged
end
def merge_sort(ary)
if ary.length <= 1
return ary
end
middle = ary.length/2
first = ary.slice(0..(middle-1))
second = ary.slice(middle..(ary.length-1))
sorted_first = merge_sort(first)
sorted_second = merge_sort(second)
return merge(sorted_first, sorted_second)
end
def make_heap(ary, stand, bottom)
child_left = 2*stand+1
child_right = 2*stand+2
max_index = stand
if child_left < bottom
max_index = child_left if ary[max_index] < ary[child_left]
max_index = child_right if ary[max_index] < ary[child_right]
elsif child_left == stand
max_index = child_left if ary[max_index] < ary[child_left]
end
if max_index != stand
tmp = ary[stand]
ary[stand] = ary[max_index]
ary[max_index] = tmp
make_heap(ary, max_index, bottom)
end
end
def heap_sort(ary)
((ary.length-1)/2).downto(0) do |i|
make_heap(ary, i, ary.length-1)
end
(ary.length-1).downto(1) do |i|
tmp = ary[0]
ary[0] = ary[i]
ary[i] = tmp
make_heap(ary, 0, i-1)
end
end
ary = [2,6,4,3,6,7,23]
heap_sort(ary)
p ary
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment