rubyでヒープソートを書いてみました

ヒープソートの説明はwikiを見てください。 ヒープソート - Wikipedia

計算量は必ず、O(n log n)で並び替えるデータの質に関係なく、高速にソート出来る点です。

ヒープソートのクラス

class HeapSort
  class << self
    def call(list)
      build_heap(list)
      (list.size - 1).downto(1) do |i|
        list[0], list[i] = list[i], list[0]
        heapify(list, 0, i)
      end
    end

    private
    def build_heap(list)
      n = list.size / 2
      n.downto(0) do |i|
        heapify(list, i, list.size)
      end
    end

    def heapify(list, idx, max)
      largest = idx
      left = idx * 2 + 1
      right = idx * 2 + 2

      largest = left if (left < max) && (list[left] > list[idx])
      largest = right if (right < max) && (list[right] > list[largest])
      if largest != idx
        list[idx], list[largest] = list[largest], list[idx]
        heapify(list, largest, max)
      end
    end
  end
end

使用してみる

pry(main)> list = [34, 6, 99, 43, 67, 37, 87, 5, 25, 85, 19, 63, 9, 35]
=> [34, 6, 99, 43, 67, 37, 87, 5, 25, 85, 19, 63, 9, 35]
pry(main)> HeapSort.call(list)
=> 13
pry(main)> list
=> [5, 6, 9, 19, 25, 34, 35, 37, 43, 63, 67, 85, 87, 99]