Module: HEAPSORT

Defined in:
lib/HEAP_SORT.rb,
lib/HEAP_SORT/version.rb

Defined Under Namespace

Classes: Error

Constant Summary collapse

VERSION = 
"0.1.0"

Instance Method Summary collapse

Instance Method Details

#heap_sort(arr) ⇒ Object 



27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/HEAP_SORT.rb', line 27

def heap_sort(arr)
  n = arr.length
  (n / 2 - 1).downto(0) do |i|
    heapify(arr, n, i)
  end

  (n - 1).downto(1) do |i|
    arr[i], arr[0] = arr[0], arr[i]
    heapify(arr, i, 0)
  end
  arr
end

#heapify(arr, n, i) ⇒ Object

frozen_string_literal: true



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/HEAP_SORT.rb', line 9

def heapify(arr, n, i)
  largest = i
  left = 2 * i + 1
  right = 2 * i + 2

  if left < n && arr[i] < arr[left]
    largest = left
  end
  if right < n && arr[largest] < arr[right]
    largest = right
  end

  if largest != i
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)
  end
end