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]