【ruby】ヒープソートを書いてみた


久々のアルゴリズム
2017年の夏にエンジニアからコンサルタントにジョブチェンジしてから、自分やチームのためにちょっとした業務自動化ツールを作ることはあったものの、エンジニアのころのようにカスタマーのために何かコードを書くことはなくなっていました。

なので、綺麗に実装するというよりは「動けば良いっしょ!」というコードばかり書いてしまっていたので、改めて自分のスキルメンテナンス/リハビリのために有名アルゴリズムのコードを書いてみることにしました。


王道のヒープソート

def heap_sort(x, n)
  i = (n - 1) / 2;
  while i >= 0 do
    down_heap(x, i, n - 1)
    i = i - 1
  end

  j = n - 1;
  while j > 0 do
    temp = x[0]
    x[0] = x[j]
    x[j] = temp
    down_heap(x, 0, j - 1)
    j = j - 1
  end
end

def down_heap(x, left, right)
  child = 0;
  parent = left;
  while parent < (right + 1) / 2 do
    cl = parent * 2 + 1
    cr = cl + 1

    if cr <= right && x[cr] > x[cl] then
      child = cr;
    else
      child = cl;
    end

    if x[parent] < x[child] then
      temp = x[parent]
      x[parent] = x[child]
      x[child] = temp
    end

    parent = child
  end
  print(x.join + "\n")
end

array = [4,6,1,3,8,5,2,9,7]
len = array.length
heap_sort(array, len)
cnt = 0
while cnt < len do
  cnt = cnt + 1
end

C言語とかだったらループの箇所は

for (int i = (n - 1) / 2; i >= 0; i--)

のように書くのですが、良い方法が思いつきませんでした…。

もしループのところのところでもっと良い実装方法をご存知の方がいらっしゃったら教えてください…。


最後まで読んでいただきありがとうございます。もしこの記事を気に入って頂けたようであればシェアをお願い致します。非常に励みになります。


コメントを残す