2021.06.03

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

mokabuu

久々のアルゴリズム
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言語とかだったらループの箇所は