Class: Sorting::HeapSort

Inherits:

Object

• Object
• Sorting::HeapSort

Extended by:

Helper

Defined in:

lib/sorting/heap_sort.rb

Constant Summary

TEST_DATA_SIZE =

100_000

Class Method Summary

• .sort!(data, l = 0, r = data.size-1) ⇒ Object

  Heap sort Comparison sort Selection Unstable Time complexity: Ω(nlogn), Ө(nlogn), O(nlogn) Space complexity: O(n) total, O(1) auxiliary Strongly random access, poor locality of reference.

Methods included from Helper

sort

Class Method Details

.sort!(data, l = 0, r = data.size-1) ⇒ Object

Heap sort Comparison sort Selection Unstable Time complexity: Ω(nlogn), Ө(nlogn), O(nlogn) Space complexity: O(n) total, O(1) auxiliary Strongly random access, poor locality of reference

# File 'lib/sorting/heap_sort.rb', line 16

def sort!(data, l=0, r=data.size-1)
  build_max_heap data
  r.downto(l).each do |i|
    data[l], data[i] = data[i], data[l]
    rebalance_max_heap data, l, l, i - 1
  end
  nil
end