読者です 読者をやめる 読者になる 読者になる

ボクココ

サービス開発を成功させるまでの歩み

プログラミング勉強基礎 その2

前回は、挿入ソートとマージソートの二つをRubyで書きました。
こんなのはとっくの前に習ってるはずだけど、意外とコーディングが面白い。就活中は変に飛ばして学習するより、こういうのやるのもいいかな、と思えてきました。
ということで今回はヒープソート。このヒープはプライオリティキュー等の応用、挿入等が便利なため、クイックソートがある現在でも良く使われる手法。アルゴリズム・イントロダクションでは関数をそれぞれの機能に分けて解説がされており、非常に分かりやすかった。
以下Rubyソースコード


#ヒープ
def parent(i)
return i/2-1
end
def left(i)
return 2*i+1
end
def right(i)
return 2*i+2
end
#指定した枝の位置を正しい位置へ移動する
def heapify(a,i)
l=left(i)
r=right(i)
if l<=a.length && a[l]!=nil && a[l]>a[i]
largest=l
else
largest=i
end
if r<=a.length && a[r]!=nil && a[r]>a[largest]
largest=r
end
if largest!=i
a[i],a[largest]=a[largest],a[i]
heapify(a,largest)
end
end
#バラバラな配列からヒープを作る
def build_heap(a)
heap_size=a.length
(a.length/2).downto(0) do |n|
heapify(a,n)
end
end
#ソート。一番下の要素を取り出すのを繰り返す
def heap_sort(a)
build_heap(a)
output=[]
len=a.length
len.step(1,-1) do |n|
a[0],a[n-1]=a[n-1],a[0]
output.push(a.pop)
heapify(a,0)
end
p output
end
#木に要素を挿入する
def heap_insert(a,key)
i=a.length
a.push(key)
while(i>1 && a[parent(i)]<key)
a[i],a[parent(i)]=a[parent(i)],a[i]
i=parent(i)
end
end

今回はエスケープたので、見やすいと思います!
前回のマージソートに比べれば、全然楽に実装できました。
さて、次回はソートの王道クイックソート。大体わかってるので躓かないで実装したいところです。